組合數列印

[北京直真筆試題]比如給定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 << "\t"<< nArray[i] << "\t" << nArray[j] << endl; //先i後j
                    cout << nAlreadySel << "\t"<< nArray[j] << "\t" << 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 4
void 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\n",i,j,k);
                                                ++count;
                                       }
                             }//end for k
                    }//end if j
           }//end for j
}//end for i
cout << "--------------count = " << count<< "-------------" << endl;
}
 
 
int main()
{
combineSelPrint(MAXN);
return 0;
}           

【思考？】：有沒有時間複雜度低的算法？或者遞歸實作的好方法？

【方法3】：遞歸實作組合數列印，C（n，m），從n個數中選出m個數（m<=n）個的全部組合列印。

有很多文章讨論如何列印全排列的，畢竟它是很多周遊問題的基礎嘛。這裡介紹的是如何列印組合數。

先看一個例子：

C(5,3) = 10
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5           

大家注意到沒有，

1 | 2 3
1 | 2 4
1 | 2 5
1 | 3 4
1 | 3 5
1 | 4 5 
------ C(4, 2)∵可以在{2, 3, 4, 5}中挑2個出來。
2 | 3 4
2 | 3 5
2 | 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 = 0
2. print ary[1..k]
3. else 
4. for i←1 to n-k+1
5. ary[index++] = A[l+i-1]
6. combination（n-i,k-1, A[l+i..n+l-1]）
7. --index
8. 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("\n");
        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---\n");
    printf("---請輸入n 和m \n---");
    scanf("%d%d",&n,&m);
 
    printf("\n---以下是輸出結果---\n");
    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

筆者調試了方法三，好用。但是筆者對其中遞歸的部分的原理甚是不解，有些疑惑，望大家介紹下。