组合数打印

[北京直真笔试题]比如给定4个数,分别为1,2,3,4。现在要求从中选取3个的组合数，不能重复。

即打印：123，124，234...。

方法1：【思路】1）将1,2,3,4存入数组中，然后从4个数中选出1个数，即为selVal；2）接下来的工作即是从剩余的3个数中选取2个数，需要存储除selVal外的剩余3个数；3）选取后打印selVal和选的2个数即可。

【分析】：时间复杂度O（n3），空间复杂度O（n）。

const int g_nCnt = 4;int g_nArr[g_nCnt] ={1,2,3,4};//从3个里面选2个数的排列方式.void selTwoFromThree(intnArray[], int nSize, int nAlreadySel){for(int i = 0; i < nSize; i++)   {           for(int j = i+1; j < nSize; j++)           {                    cout << nAlreadySel << "	"<< nArray[i] << "	" << nArray[j] << endl; //先i后j                    cout << nAlreadySel << "	"<< nArray[j] << "	" << nArray[i] << endl; //先j后i           }  }} void printArray(intnArray[], int nSize){int nAleardySel = 0;for(int i = 0; i < nSize; i++){           int *pArrAdd = new int[3];           int k = 0;           nAleardySel = nArray[i];           for(int j = 0; j < nSize; j++)           {                    if(nArray[j] != nAleardySel)                    {                             pArrAdd[k++] = nArray[j];                    }//end if           }//end for j                     selTwoFromThree(pArrAdd,g_nCnt-1,nAleardySel);           cout << endl;}//end fori}

方法2：【思路】 将4个数中选择的3个数看做百位数，因此就变成了打印的过程，变成了从4个数中选3个数组成的全排列444=64个中选择百位、十位、个位不重复的432=24个数的过程。

【分析】：时间复杂度O（n3），空间复杂度O（1）。不需要额外的开辟空间。

#define MAXN 4void combineSelPrint(intmaxCnt){static int count = 0;for(int i=1;i<=MAXN;i++)//百位的情况{           for(int j=1;j<=MAXN;j++)//十位的情况           {                    if(j != i)                    {                             for(int k=1;k<=MAXN;k++)//个位的情况                             {                                       if(k != j && k != i)                                       {                                                printf("%d,%d,%d
",i,j,k);                                                ++count;                                       }                             }//end for k                    }//end if j           }//end for j}//end for icout << "--------------count = " << count<< "-------------" << endl;}  int main(){combineSelPrint(MAXN);return 0;}

【思考？】：有没有时间复杂度低的算法？或者递归实现的好方法？

【方法3】：递归实现组合数打印，C（n，m），从n个数中选出m个数（m<=n）个的全部组合打印。

有很多文章讨论如何打印全排列的，毕竟它是很多遍历问题的基础嘛。这里介绍的是如何打印组合数。
先看一个例子：

C(5,3) = 101 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5

大家注意到没有，

1 | 2 31 | 2 41 | 2 51 | 3 41 | 3 51 | 4 5 ------ C(4, 2)∵可以在{2, 3, 4, 5}中挑2个出来。2 | 3 42 | 3 52 | 4 5 ------ C(3, 2)∵可以在{3, 4, 5}中挑2个出来。3 | 4 5 ------ C(2, 2)∵只能在{4, 5}中挑2个出来。

这样就很容易写出递归算法来。

Algorithm combination（n, k, A[l..n+l-1]）1. if k = 02. print ary[1..k]3. else 4. for i←1 to n-k+15. ary[index++] = A[l+i-1]6. combination（n-i,k-1, A[l+i..n+l-1]）7. --index8. endfor

大家可能会疑惑干嘛要弄出个index，还有一加一减的（你手工算一下就知道了）。

【实现部分】

int *dst_array,top=0;//中间数组，存放中间求解过程，count计数所有的组合个数int cnt = 0; //打印长度为n的数组元素static void printA(int*parray,int n){    int i;    for(i=0;i<n;i++)    {        printf("%d ",parray[i]);    }} //递归打印组合数static  void print_combine(int *pArray,int n,int m){    if(n < m || m==0)      {           return ;//情况一：不符合条件，返回    }     print_combine(pArray+1,n-1,m);//情况二：不包含当前元素的所有的组合     dst_array[top++]=pArray[0];//情况三：包含当前元素    if(m==1)     {  //情况三-1：截止到当前元素        printA(dst_array,top);        printf("
");        cnt++;        top--;        return;    }     print_combine(pArray+1,n-1,m-1);//情况三-2：包含当前元素但尚未截止    top--;//返回前恢复top值} int main(){    int n,m,*parray;//存放数据的数组，及n和m    printf("---以下实现从n个数中选出m个数的全组合打印(n个数为1,2,3....n---
");    printf("---请输入n 和m 
---");    scanf("%d%d",&n,&m);     printf("
---以下是输出结果---
");    parray=(int *)malloc(sizeof(int)*n);    dst_array=(int *)malloc(sizeof(int)*m);     int i;    for(i=0;i<n;i++)    {           //初始化数组        //scanf("%d",&parray[i]);           parray[i] = i+1;    }    print_combine(parray,n,m);//求数组中所有数的组合     printf("=====C（%d，%d）共计：%d个=====",n,m,cnt);     free(parray);    free(dst_array);    return 0;}

方法三参考：http://bbs.pfan.cn/post-270256.html

http://blog.csdn.net/challenge_c_plusplus/article/details/6641950

笔者调试了方法三，好用。但是笔者对其中递归的部分的原理甚是不解，有些疑惑，望大家介绍下。