組合數列印

組合數列印

//[北京直真筆試題]比如給定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;

          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個數組成的全排列4*4*4=64個中選擇百位、十位、個位不重複的4*3*2=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 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 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);

          //初始化數組

       //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

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