求一个计算排列组合的算法

eveson

别告诉我去baidu，google之类的，如果你调试过给我发一下。

mcemil

我知道一种非递归的高效率的球组合数方法，基本描述如下（没有证明，但经过acm的多次考验都是正确的）
假设5个元素取3个，以数组s表示该位置上的元素是否被选中，1选中，0没有选中。
初始为 ,表示第一个组合为前n个数。     
1 1 1 0 0      // 1,2,3
然后循环，每次从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为  
  “01”组合，同时将其左边的所有“1”全部移动到数组的最左端，此时便得到了一个新的组合
重复这一直到找不到“10”组合:

1 1 [1 0] 0  => 1 1 [0 1] 0  //1,2,4

1 [1 0] 1 0 =>  1 [0 1] 1 0 //1,3 ,4
......
....
0 0 1 1 1 // 3,4,5
以上的例子没有出现“同时将其左边的所有“1”全部移动到数组的最左端”这种情况，具体来说如下：
假设出现了   0 1 [1 0]则要2部变换，先是0 1 [0 1] 再是   [1 0] 0 1

ubuntuer

1. 
   
2. void permutate(char* str, int begin, int end)
   
3. {
   
4.   int i;
   
5.   if(begin == end)
   
6.     printf("%s\n",str);
   
7.   else
   
8.    {
   
9.      for(i=begin; i<end; i++)
   
10.       {
    
11.         swap(str+begin,str+i);
    
12.         permutate(str, begin+1, end);
    
13.         swap(str+begin,str+i);            
    
14.       }               
    
15.    }     
    
16. }
    

复制代码

要这种？

eveson

不要递归的，只需要给个组合计算的就行了，不考虑排列的了。

redspider

相当牛，没调试过是不是不能发给您老人家

bidongliang

std::next_permutation不就得了？

eveson

原帖由 mcemil 于 2009-8-10 17:53 发表
我知道一种非递归的高效率的球组合数方法，基本描述如下（没有证明，但经过acm的多次考验都是正确的）
假设5个元素取3个，以数组s表示该位置上的元素是否被选中，1选中，0没有选中。
初始为 ,表示第一个组合为 ...

你说的是这个吧，网上找的，有点问题，不过我已经调试好了，还加了打印，文件记录，代码风格很不好，再整理下

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. #include "stdafx.h"
   
6. 
   
7. /***********************
   
8. 
   
9. * 计算一个集合的组合
   
10. 
    
11. **********************/
    
12. 
    
13. #include<stdlib.h>
    
14. 
    
15. 
    
16. /*输出某个组合*/
    
17. 
    
18. void OutputCom(FILE *fp,const int elements[], int *flags, int length)
    
19. 
    
20. {
    
21. 
    
22.          int i;
    
23.        
    
24.          for(i=0; i<length; i++)
    
25. 
    
26.          {
    
27. 
    
28.                    if(flags[i]==1)
    
29. 
    
30.                    {
    
31.                                                         //printf("%d ",elements[i]);
    
32. 
    
33.                                                         fprintf(fp, "%u ",elements[i] );
    
34. 
    
35. 
    
36.                    }
    
37. 
    
38.          }
    
39.                  //printf("\n");
    
40. 
    
41.          fprintf(fp, "\n");
    
42. 
    
43. }
    
44. 
    
45. /*计算组合*/
    
46. 
    
47. int GenCom(FILE *fp,const int elements[], int setLg, int k)
    
48. 
    
49. //elements:集合元素; setLg:集合长度; k:从集合中要选取的元素个数
    
50. 
    
51. {
    
52. 
    
53.          if(k>setLg || k<=0)
    
54. 
    
55.                    return -1;
    
56. 
    
57. 
    
58. 
    
59.          int i,j;                   //循环变量
    
60. 
    
61.          int has10; //是否有"10"组合的标志:1-有;0-无
    
62. 
    
63.          int bound; //第一个"10"组合的索引
    
64. 
    
65.          int num1;           //"10"组合左边的"1"的个数
    
66. 
    
67.          int *flags = (int *)malloc(setLg*sizeof(int));//与元素集合对应的标志:1-被选中;0-未被选中
    
68. 
    
69.          //初始化,将标志的前k个元素置1,表示第一个组合为前k个数
    
70.                 printf("正在生成......\n");
    
71.          for(i=0; i<k; i++)
    
72. 
    
73.                    flags[i]=1;
    
74. 
    
75.          for(i=k; i<setLg; i++)
    
76. 
    
77.                    flags[i]=0;
    
78. 
    
79. 
    
80. 
    
81.          OutputCom(fp,elements, flags, setLg);//输出初始化的组合
    
82. 
    
83.          /*
    
84. 
    
85.                    从左到右扫描标志的"10"组合，找到第一个"10"组合后将其变为"01"组合，同时将其左边的所有"1"全部移动到数组的最左端
    
86. 
    
87.          */
    
88. 
    
89.          while(1)
    
90. 
    
91.          {
    
92. 
    
93.                    num1 = 0;
    
94. 
    
95.                    has10= 0;
    
96. 
    
97.                    for(i=0; i<setLg-1; i++)
    
98. 
    
99.                    {
    
100. 
     
101.                             if(flags[i]==1 && flags[i+1]==0)//找到第一个"10"组合
     
102. 
     
103.                             {
     
104. 
     
105.                                      bound = i;
     
106. 
     
107. 
     
108. 
     
109.                                      flags[i]=0;//将该"10"组合变为"01"组合
     
110. 
     
111.                                      flags[i+1]=1;
     
112. 
     
113. 
     
114. 
     
115.                                      for(j=0; j<num1; j++)//将其左边的所有"1"全部移动到数组的最左端
     
116. 
     
117.                                      {
     
118. 
     
119.                                                flags[j]=1;
     
120. 
     
121.                                      }
     
122. 
     
123.                                      for(j=num1; j<bound; j++)
     
124. 
     
125.                                      {
     
126. 
     
127.                                                flags[j]=0;
     
128. 
     
129.                                      }
     
130. 
     
131. 
     
132. 
     
133.                                      has10 = 1;
     
134. 
     
135.                                      break;
     
136. 
     
137.                             }
     
138. 
     
139.                             else if(flags[i]==1)
     
140. 
     
141.                             {
     
142. 
     
143.                                      num1++;
     
144. 
     
145.                             }
     
146. 
     
147.                    }
     
148. 
     
149.                    if(has10==0)//没有"10"组合了,代表组合计算完毕
     
150. 
     
151.                             break;
     
152. 
     
153.                    OutputCom(fp,elements, flags, setLg);
     
154. 
     
155.          }
     
156. 
     
157.          
     
158. 
     
159.          return 1;
     
160. 
     
161. }
     
162. 
     
163. int ComputeCom( int nSpaceNum, int nElemNum )
     
164. {
     
165.         int j;
     
166.         int denominator = 1;
     
167.         int numerator = 1;
     
168.         int nCompNum = 1;
     
169.         if ( 0 == nElemNum )
     
170.         {
     
171.                 return 1;
     
172.         }
     
173.         if ( nElemNum > nSpaceNum / 2 + 1)
     
174.         {
     
175.                 nElemNum = nSpaceNum - nElemNum;
     
176.         }
     
177.         //计算单个组合的个数
     
178.         for( j = 1; j <= nElemNum; j++ )
     
179.         {
     
180.                 numerator *= (nSpaceNum - (j-1));
     
181.                 denominator *= j;
     
182.         }
     
183.         nCompNum = numerator / denominator;
     
184.         return nCompNum;
     
185. }
     
186. 
     
187. /*测试*/
     
188. 
     
189. int main()
     
190. 
     
191. {
     
192.         int dwAllComNum;
     
193.         FILE *fp;
     
194.         const int elements[33]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33};
     
195.         int setLg=33;
     
196.         fp = fopen("f:/All.txt","w");
     
197.         if (NULL == fp)
     
198.         {
     
199.                 printf("打开文件失败");
     
200. 
     
201.                 return -1;
     
202.         }
     
203. 
     
204. 
     
205.         dwAllComNum = ComputeCom(33,6);
     
206.         printf("共有 %d 种组合\n",dwAllComNum);
     
207.                  getchar();
     
208. 
     
209.          GenCom(fp,elements, setLg, 6);
     
210.                  fclose(fp);
     
211. 
     
212.         printf("运行完毕\n");
     
213.                  getchar();
     
214.          return 0;
     
215. 
     
216. }
     
217. 
     
218. 
     

复制代码

eveson

原帖由 bidongliang 于 2009-8-10 19:11 发表
std::next_permutation不就得了？

要纯c的，没写清除要求，大家的思维还真广阔