C(n,m)的组合问题

// 回溯算法

1. void   comb_back(int a[],int   m,int   r)    
2. {   
3.        
4. int   i,j,k=0;    
5.      i=0,a[i]=1;    
6. do  
7. {    
8.     if (a[i]-i<=m-r+1)   
9.     {    
10.           // 相等就找到组合     
11.           if (i==r-1)   
12.           {      
13.           printf( "第%d组： ",++k);    
14.           for(j=0;j <r;j++)   
15.           printf( "%d ",a[j]);printf( "/n ");    
16.              
17.           // 最后的一个元素加1    
18.           a[i]++;                      
19.           continue;   
20.           }    
21.        
22.         i++;   //向前试探    
23.         a[i]=a[i-1]+1;   
24.         }    
25.     else  
26.     {   
27.          //回溯    
28.           if(i==0)     
29.              return;//已找到了全部解    
30.           a[--i]++;   
31.     }    
32. }while(1);    
33. }  

 

Code:

1. // Function:从n个数中选择m个数进行组合的非递归算法。   
2. /*  
3. 首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。   
4. 然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为   
5. “01”组合，同时将其左边的所有“1”全部移动到数组的最左端。   
6. 当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得   
7. 到了最后一个组合。   
8. 例如求5中选3的组合：   
9. 1 1 1 0 0 //1,2,3   
10. 1 1 0 1 0 //1,2,4   
11. 1 0 1 1 0 //1,3,4   
12. 0 1 1 1 0 //2,3,4   
13. 1 1 0 0 1 //1,2,5   
14. 1 0 1 0 1 //1,3,5   
15. 0 1 1 0 1 //2,3,5   
16. 1 0 0 1 1 //1,4,5   
17. 0 1 0 1 1 //2,4,5   
18. 0 0 1 1 1 //3,4,5   
19. */  
20.   
21. #include "stdafx.h"   
22. #include <stdio.h>   
23. #include <stdlib.h>   
24.   
25. void C(int N, int M, int *Num)   
26. {   
27.     int i;   
28.     bool ifok = false;   
29.     // 10前面连续0的个数   
30.     int iZero = 0;   
31.     // 10前面连续1的个数   
32.     int iOne = 0;   
33.     // 初始化第一个组合   
34.     for (i=0; i<M; i++)   
35.     {   
36.         Num[i] = 1;   
37.         printf("%d", i+1);   
38.     }   
39.     printf("/n");   
40.   
41.     // N-M个数为0   
42.     for (i=M; i<N; i++)   
43.         Num[i] = 0;   
44.     if (M == N)   
45.         ifok = true;   
46.   
47. while(!ifok)   
48. {   
49.     iOne = 0;   
50.     iZero = 0;   
51.     // 从第一个数开始找10   
52.        for (i=0; i<N; i++)   
53.        {   
54.            // 找到10   
55.            if ( 1 == Num[i] && 0 == Num[i+1])   
56.            {   
57.                 Num[i] = 0;   
58.                 Num[i+1] = 1;   
59.                 break;   
60.                    
61.            }   
62.   
63.           // 找到1且下一个不是0   
64.            else if (1 == Num[i] && 0 != Num[i+1])   
65.            {   
66.                iOne++;   
67.            }   
68.            // 计算连续0的个数   
69.            else if (0 == Num[i])   
70.            {   
71.                 iZero++;   
72.            }   
73.        }   
74.        
75.        if (iZero)   
76.        {   
77.             // 把左边的所有1移到左端   
78.                 for (i=0; i<iOne; i++)   
79.                 {   
80.                   Num[i] = 1;   
81.                 }   
82.   
83.                 for (i=iOne; i<iOne+iZero; i++)   
84.                 {   
85.                     Num[i] = 0;   
86.                 }   
87.   
88.        }   
89.         // 输出结果   
90.         for (i=0; i<N; i++)   
91.         {   
92.             if (Num[i] == 1)   
93.                 printf("%d", i+1);   
94.         }   
95.         // 换行   
96.         printf("/n");   
97.   
98.         // 判断是否输出了所有的组合   
99.        for (i=N-M; i<N; i++)   
100.        {   
101.             if (0 == Num[i])   
102.             break;   
103.        }   
104.   
105.        if (Num[N-1] != 0 && i == N)   
106.            ifok = true;   
107.     }   
108. }   
109. int main(void)   
110. {   
111.     int N;   
112.     int M;   
113.     scanf("%d%d", &N, &M);   
114.     int *Num = (int *)malloc(sizeof(int)*N);   
115.     C( N,  M,Num);   
116.     free(Num);   
117.     return 0;   
118. }   
119.   

Code:

1.  // 递归算法   
2.   
3. /// 求从数组a[1..n]中任选m个元素的所有组合。   
4. /// a[1..n]表示候选集，n为候选集大小，n>=m>0。   
5. /// b[1..M]用来存储当前组合中的元素(这里存储的是元素下标)，   
6. /// 常量M表示满足条件的一个组合中元素的个数，M=m，这两个参数仅用来输出结果。   
7. void combine( int a[], int n, int m,  int b[], const int M )   
8. {    
9.  for(int i=n; i>=m; i--)   // 注意这里的循环范围   
10.  {   
11.   b[m-1] = i - 1;   
12.   if (m > 1)   
13.    combine(a,i-1,m-1,b,M);   
14.   else                     // m == 1, 输出一个组合   
15.   {      
16.    for(int j=0; j<M; j++)   
17.     printf("%d", a[b[j]]);   
18.     printf("/n");   
19.   }   
20.   }