求组合数、排列数等

Posted on by

最近写程序一直遇到组合数，排列数等问题。文章介绍程序实现全排列$A_{n}^{n}$、组合$C_{n}^{k}$ 中每个项的列举。

全排列$A_{n}^{n}$ 有顺序的排列n 个数；

组合$C_{n}^{k}$ 从n 个数中选取k 个进行无顺序的组合；

附：一般性的排列$A_{n}^{k}$ 可以通过组合和全排列一起完成。

组合数

参考 wiki combination

原则是每组找到的数右边的数值总比左边大，而每次都增加最右边能够增加的值到不能增加为止。第一组数从（0,1,2,……,k-1）开始，指针开始指向最后一个数字，如果指针指到了第一个数字且第一个数字不能再增大则找到所有组数，结束。每次加一指针所指数字直至不超过该数后面的数字（当数字本身就是最后一个数字时，则增加到k-1），然后指针向前移一，新指针位置的值加一，并将新指针位置后的值按照新指针所指的值递加一作为新的值。

n=7，k=5 举例如下（红色为指针位置）：

0  1  2  3 4               //初始 0,1,2,……,k-1

0  1  2  3  5

0  1  2  3  6              //指针所指数（6）不能再增加了

0  1  2  4  5              //指针前移，所指数（3）加一，其后的数字按（3）递加一

0  1  2  4  6             //指针所指数6 不能再增加了

0  1  2  5  6             //指针所指数（5）不能再增加了，否则比后面的数大了

0  1  3  4  5             //指针前移，所指数（2）加一，其后的数字按（2）递加一

0  1  3  4  6

代码：

   1: int a[100];

   2: int cur;

   3: for(int i=0; i<k; ++i){

   4:     a[i] = i;        //初始值0,1,2,...,k-1

   5: }

   6: cur = k-1;

   7: do{

   8:     if(a[cur]-cur <= n-k){    //指针所指数字可以继续增大

   9:         //这里打印出a[]，可以得到所有组合数

  10:         a[cur]++;

  11:         continue;

  12:     }else{

  13:         if(cur==0){

  14:             break;    //指针指向第一个数，结束

  15:         }

  16:         --cur;

  17:         ++a[cur];

  18:         for(int i=1; i<k-cur; ++i){

  19:            a[cur+i] = a[cur]+i;     

  20:        }

  21:        if(a[cur]-cur<m-r){

  22:            cur=k-1;            //最后一个值还可以增加，指针移动到最后

  23:        }

  24:     }

  25: }while(1);

下面根据传入的一组组合数求下一个组合数（返回true），如果没有则返回false（该组合数已经是最后一个组合数）；

   1: bool next_combination(int* const a, int asize, int inall){

   2:     int size = asize;

   3:     int i;

   4:     int value;

   5:  

   6:     // 0 1 2 3 4 

   7:     if(a[0] >= (inall-size)){

   8:         return false;

   9:     }

  10:  

  11:     for(i = size-1; i > 0; --i){

  12:         if(a[i] < inall-(size-i)){

  13:             break;

  14:         }

  15:     }

  16:     

  17:     value = a[i];

  18:     for(;i < size; ++i){

  19:         ++value;

  20:         a[i] = value;

  21:     }

  22:     return true;

  23: }

 

排列数

参考 wiki permutation

原则是将顺序的（1,2,……,n-1）排列通过置换变为逆序的排列（n-1,n-2,……,1）。每次从最后一个数字倒序开始，找到第一个后一个数大于前一个数，按顺序分别记作第i-1 和第i 个数，再倒序找到第一个大于第i-1 个数的数，将该数与第i-1 个数置换，最后将从第i 个数到最后一个数位置倒序。

n=4 举例如下：

第i-1 和第i 个数               置  换                         倒   序

                                                                            1  2  3  4         （1）

1  2  3  4                           1  2  4  3                     1  2  4  3         （2）       

1  2  4  3                           1  3  4  2                     1  3  2  4         （3）

1  3  2  4                           1  3  4  2                     1  3  4  2         （4）

1  3  4  2                           1  4  3  2                     1  4  2  3         （5）

1  4  2  3                           1  4  3  2                     1  4  3  2         （6）

1  4  3  2                           2  4  3  1                     2  1  3  4         （7）

2  1  3  4                           2  1  4 3                     2  1  4  3         （8）

2  1  4  3                           2  3  4  1                     2  3  1  4         （9）

2  3  1  4                           2  3  4  1                     2  3  4  1         （10）

2  3  4  1                           2  4  3  1                     2  4  1  3         （11）

2  4  1  3                           2  4  3  1                     2  4  3  1         （12）

2  4  3  1                           3  4  2  1                     3  1  2  4         （13）

3  1  2  4                           3  1  4  2                     3  1  4  2         （14）

3  1  4  2                           3  2  4  1                     3  2  1  4         （15）

3  2  1  4                           3  2  4 1                     3  2  4  1         （16）

3  2  4  1                           3  4  2  1                     3  4  1  2         （17）

3  4  1  2                           3  4  2  1                     3  4  2  1         （18）

3  4  2  1                           4  3  2  1                     4  1  2  3         （19）

4  1  2  3                           4  1  3  2                     4  1  3  2         （20）

4  1  3  2                           4  2  3  1                     4  2  1  3         （21）

4  2  1  3                           4  2  3 1                     4  2  3  1         （22）

4  2  3  1                           4  3  2  1                     4  3  1  2         （23）

4  3  1  2                           4  3  2  1                     4  3  2  1         （24）

第一列红色数字表示倒序第一组后面数字大于前面的数字，中划线的数字表示要和第i-1 个数字置换的数字（也就是倒序第一个比第i-1 个数大的数字）。第二列蓝色为需要倒序的数字，从第i 个数字到最后一个数字。最后一列为所有24 个结果。

下面的代码输出全排列的下一组数，到末尾返回false：

   1: bool next_permutation(int* const v, int vsize){

   2:     int size = vsize;

   3:     int i, j;

   4:     int temp;

   5:  

   6:     //stop at the first place where the latter element is greater than the previous

   7:     for(i = size-1; (i>0)&&(v[i]<v[i-1]); --i);

   8:  

   9:     if(0 == i) return false; //at the end of the permutation

  10:  

  11:     //find first element after v.at(i-1) greater than it

  12:     for(j = size-1; j > i&&v[j]<v[i-1]; --j);

  13:  

  14:     temp = v[j];

  15:     v[j] = v[i-1];

  16:     v[i-1] = temp;

  17:     

  18:     //inverse from v.at(i) to v.at(size-1)

  19:     for(j = size-1; i < j; --j, ++i){

  20:         temp = v[i];

  21:         v[i] = v[j];

  22:         v[j] = temp;

  23:     }

  24:  

  25:     return true;

  26: }

 

允许重复元素的全排列

之前的全排列不允许重复元素，即不允许（0,0,0,……,0）或者（1,k-1,……,k-1）这样允许重复元素的全排列，允许重复元素的全排列好比从n 个一样的桶里面选择一个带编号的球，每个桶k 个球，编号从0到k-1。共计有nk 种。

原则是模拟k 进制不断增加最低位数：

n = 3，k = 2 的例子：

0  0  0

0  0  1

0  1  0

0  1  1

1  0  0

1  0  1

1  1  0

1  1  1

代码：

   1: bool JU = true;

   2: for(i=0; i<n; ++i){

   3:     a[i] = 0;

   4: }

   5: do{

   6:     for(i=0; i<n; ++i){

   7:         printf("%d ", a[i]);

   8:     }

   9:     printf("\n");

  10:     

  11:     ++a[0];

  12:     if(a[0] < k){

  13:         continue;

  14:     }else{      

  15:         a[0] = 0;

  16:         for(i=1; i<n; ++i){

  17:             ++a[i];

  18:             if((i == (n-1))&(a[i] == k)){

  19:                 JU = false;

  20:                 break;

  21:             }

  22:             if(a[i] == k){

  23:                 a[i] = 0;

  24:             }else{

  25:                 break;

  26:             }

  27:         }

  28:     }

  29: }while(JU);

《求组合数、排列数等》上有2条评论

回复 navylq 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。