C++全组合算法（ok）

jxmjg

1. #include <iostream>
2. #include <vector>
4. using namespace std;
6. //求长度为number的组合
7. /*
8.   参数：
9.   v：基础元素集合
10.   cur采用v：当前递归过程中的中间组合变量
11.   cur采用index:当前递归处理到v中第几个元素了
12.   number:要求的组合的长度值
13.   result:用于保存组合结果
14. */
15. template<class T>
16. void Combination采用n(const vector<T>& v, vector<T>& cur采用v, int cur采用index, int number, vector<vector<T>>& result) {
18.     if (number == 0) {
19.         result.push采用back(cur采用v);
20.         return;
21.     }
23.     if (cur采用index >= v.size()) {
24.         return;
25.     }
27.     cur采用v.push采用back(v[cur采用index]);
28.     Combination采用n(v, cur采用v, cur采用index + 1, number - 1, result);
29.     cur采用v.pop采用back();
30.     Combination采用n(v, cur采用v, cur采用index + 1, number, result);
31. }
33. //求全组合，对于长度为n的v，组合的种类数一共有2^n-1种
34. /*
35.   参数:
36.   v是基础元素集合
37.   result用于保存所有组合结果
38. */
39. template<class T>
40. void Combination(const vector<T>& v, const int &num,vector<vector<T>>& result)
41. {
42.     if (v.empty()) {
43.         return;
44.     }
45.     else if (v.size() == 1) {
46.         result.push采用back(v);
47.         return;
48.     }
50.     //求不同长度的组合
51.     vector<int> temp采用v;
52.     for (int i = num; i <= v.size(); ++i) {
53.         Combination采用n(v, temp采用v, 0, i, result);
54.     }
56. }
58. int main(int argc, char* argv[])
59. {
60.     vector<int> v{ 1,2,3 ,4,5,6,7,8,9,10};
61.     vector<vector<int>> result;
62.     Combination(v, 5,result);
63.     vector<int> v2;
65.    
66.     for (auto& a : result) {
67.         for (auto& b : a) {
68.             cout << b<<"  ";
69.         }
70.         cout << endl;
71.     }
72.     cout << result.size() << endl;
73.     return 0;
74. }

复制代码

jxmjg

思路一:全排列剪枝
组合问题实际是排列问题在不考虑数字顺序的情况
在[1,n]这n个数中,选择k个数,那么我们首先选择第一个数,然后选择第二个数,然后选择第三个数,直到选择到第k个数。
既然组合问题它不考虑数字的顺序,那么我们不妨永远保持它从小到大,即在选择数的时候,要求这个数要比已经选择的所有数大。

1.     vector<int> temp;
2.     vector<vector<int>> results;
3.     void dfs(int n,int k,int level)
4.     {
5.         //level表示目前在取第几个数
6.         if(level==k+1)
7.         {
8.             results.push采用back(temp);
9.             return;
10.         }
11.         int i=1;
12.         if(temp.size()!=0)
13.         {
14.             i=temp[temp.size()-1]+1;//即temp种最大的数+1
15.         }
17.         while(i<=n)
18.         {
19.             temp.push采用back(i);
20.             dfs(n,k,level+1);
21.             temp.pop采用back();
22.             i++;
23.         }
24.     }

复制代码

jxmjg

思路二:
我们同样采用DFS算法,但是我们的思路是,依次考察1,2,…,k这些数,分别考虑它们在不在结果中,这种算法更加优越,因为它无形中就暗含着结果中数字是从小到大排序的。

1.     vector<int> temp;
2.     vector<vector<int>> results;
3.     void dfs(int n,int k,int cur)
4.     {
5.         //我们的思路是考察cur这个数是不是在temp中，一种是在，一种是不在
6.         //考察cur这个数时,[1,cur-1]都已经考察完了
7.         if(temp.size()==k)
8.         {
9.             results.push采用back(temp);
10.             return;
11.         }
12.         //如果temp中的数的个数加上剩下没考虑的数 的个数之和小于k，这种就没必要选取了
13.         if(n-cur+1+temp.size()<k)
14.         {
15.             return;
16.         }
18.         //cur在temp中
19.         temp.push采用back(cur);
20.         dfs(n,k,cur+1);
21.         temp.pop采用back();
23.         //cur不在temp中
24.         dfs(n,k,cur+1);
26.     }

复制代码

jxmjg

1. #include<iostream>
2. using namespace std;
3. int n, k;
5. /*
6. *递归函数。
7. *参数u：枚举了多少位数
8. *参数sum：选择了多少
9. *参数state：用二进制的1和0两种状态表示五个数的选与不选的状态
10. *k：要选择的数， 5选3 中的3
11. *n：在多少里面选， 5选3中的5
12. */
13. void dfs(int u, int sum, int state)
14. {
15.     /* n - u ：表示还未枚举的数
16.      * sum：表示已经选择的数
17.      * 整体表示，已选择的数加上最后可选择的数如果还不够总共需要选择的数的话就可以返回了
18.     */
19.     if(sum + （n - u） < k) return;
20.    
21.     //当选择的数够3个了的时候
22.     if (sum == k){
23.         for ( int i = 0; i < n; i++ ) {
24.             if ( state>>i & 1 ){
25.                 cout<<i+1<<' ';
26.             }
27.         }
28.         cout<<endl;
29.         return;
30.     }
31.    
32.     //当所有数都枚举完了的时候
33.     if ( u == n ) return;
34.    
35.     //表示这个数被选的情况
36.         dfs(u+1,sum+1,state | 1<<u);
37.     //表示这个数没有被选的情况
38.     dfs(u+1,sum,state);
39. }
41. int main(){
42.     cin>>n>>k;
43.    
44.     //将所有的数都遍历一遍，选与被选都考虑了一遍！
45.     dfs(0,0,0);
46.     return 0;
47. }
50. int n=5, k=3;
52. 1，2，3
54. 1，2，4
56. 1，3，4
58. 2，3，4
60. 1，2，5
62. 1，3，5
64. 2，3，5
66. 1，4，5
68. 2，4，5
70. 3，4，5

复制代码

jxmjg

非递归做法
参考链接

非递归的方式我感觉非常的巧妙而且有意思，而且相对递归会比较容易理解很多，毕竟递归还是比较难的。

思路：

我们还是以五个数里面选择数三个数为例。

由上面递归的做法可以知道，每个数都有选与不选两种可能。

可以假设一个容量为五的数组里面，我们将选的赋值为1，将没选的赋值为0。

我们可以转化成用二进制的形式，那每一种组合就相当于一个数值，因为如果在0~31个范围里面只选取三个数赋值为1的话，在不同的位置赋值对于一个二进制数来说都是不同的数值。我们换算成十进制从左往右算。

1，2，3（1，1，1，0，0）—— 7

1，2，4（1，1，0，1，0）—— 11

1，3，4（1，0，1，1，0）—— 13

2，3，4（0，1，1，1，0）—— 14

1，2，5（1，1，0，0，1）—— 19

1，3，5（1，0，1，0，1）—— 21

2，3，5（0，1，1，0，1）—— 22

1，4，5（1，0，0，1，1）—— 25

2，4，5（0，1，0，1，1）—— 26

3，4，5（0，0，1，1，1）—— 28

我们可以看出如果用二进制的形式来表示选与不选，通过位移1的位置我们可以得到不同的数值，也就是不同的组合，而且如果按照一定的规则位移的话你可以发现他是刚好从小到大的排序的。

这边我们要注意的是我们是从左往右计算，位移的。

所以是右大左小，每最右边的那个1往右位移一位的时候就相当于进一了，不管后面的1怎么放都会比前面的那个组合大，所以后面的1就要从最左边也就是最小的那边开始枚举。

代码实现

n选k，初始化n的个数，将他们都赋值为0，然后将前面k个数赋值为1，表示最小的二进制数。
如果找到下一个比较大的数呢，那就是位移，每次都是只位移一位，所以可以将右边的0赋值为1，将原本的1改为0，就是遇到10的都全部改为01，那么这个数就变大了。
每次位移的时候都要将位移的这个1后面的全部1都移到最左边，这样才是最小的数。
代码如下：

1. #include <iostream>
2. using namespace std;
4. #define NUM 5
5. int M[NUM];
7. /*输出*/
8. void output(int m[])
9. {
10.         for(int i = 0 ;i < NUM; i++){
11.                 if(M[i]){
12.                         cout<<m[i];
13.                 }
14. //cout<<M[i];
15.         }
16.         cout<<endl;
17. }
20. /*将前面的数从新排序，将1都移至最左端*/
21. void paixu(int k)
22. {
23.         for(int i = k;i >= 0; i--){
24.                 for(int j = i-1; j>=0; j--){
25.                         if(M[i]>M[j]){
26.                                 int tmp = M[i];
27.                                 M[i] = M[j];
28.                                 M[j] = tmp;
29.                         }
30.                 }       
31.         }
32. }
34. /*判断是否结束*/
35. int jdgover(int n)
36. {
37.         for(int i = NUM-n;i < NUM ; i++){
38.                 if(M[i] == 0)
39.                 return 0;
40.         }
41.         return 1;
42. }
44. /*主函数*/
45. int main()
46. {
47.         int m[5] = {1,2,3,4,5};
48.         int i,n;
49.         cout<<"请输入你要从五个数中选几个数进行组合:";
50.         cin>>n;
51.         for(int k = 0;k<n;k++){
52.                 M[k] = 1;
53.         }
54. output(m);
55.        
56.         /*遍历，直到1从左边全部移到右边*/
57.         for (i = 0;i <NUM ;i++){
58.                 if(M[i] == 1 && M[i+1] == 0){
59.                                 M[i] = 0;
60.                                 M[i+1] = 1;
61.                                 paixu(i);       
62.                                 output(m);
63.                                 i = -1;
64.                         }       
65.                         if(jdgover(n))
66.                         break;       
67.                 }               
68. }

复制代码

jxmjg

每组样例输出结束后要再输出一个回车。
输入
abc
输出
abc
acb
bac
bca
cab
cba

class solution {
public:
        void perm(string str, int start, int end) {
                if (start == end) {
                        for (int i = 0; i <= end; i++)
                                cout << str[i];
                        cout << endl;
                }
                else
                {
                        for (int j = start; j <= end; j++) {
                                swap(str[j], str[start]);
                                perm(str, start + 1, end);
                                swap(str[j], str[start]);
                        }
                }
        }
};