// 求从m个数据中任取n个数据的所有组合
// [in]chars -- 存放m个数据
// [in]m -- 数据个数
// [in]n -- 需要从m个数中取的数据的个数
// [out]set -- 存放所有的组合
// [inout]row -- 组合个数
// [in]col -- 当前取到第几个数据
// 思路：每次从集合中按顺序选择1个，然后进入递归取下一个；下一个数据只能从当前数据的后面的数据中任取一个
// 为了降低实际复杂度，当后面的数据个数不够时就不再取（通过for循环控制）。由于后面的组合与前面
// 的组合存在一定的同构性，因此，在获得一个组合后，直接把该组合的前面若干数据复制作为下一个组合的数据
template <class T>
void GetCombination(T *data, long m, long n,  T *set[], long &row, long col)
{
 long  i, j;

 if(n == 0)
 {
  ++row;
  // 直接把该组合的前面col-1个数据复制作为下一个组合的数据
  for(j=0; j<col-1; ++j)
   set[row][j] = set[row-1][j];
  
  return;
 }

 for(i=0; i<=m-n; ++i)
 {
  set[row][col++] = data[i];
  GetPermutation(data+i+1, m-1-i, n-1, set, row, col);
  --col;
 }
}

评论