组合(Combination)指的是对于一个元素个数为\(n\)的集合\(A\)，从集合的\(n\)个元素中任取\(m(0 \leq m \leq n)\)个元素组成所有集合得到的结果。全组合(Full Combination)为从元素个数为\(n\)的集合\(A\)中所有元素数量为\(m(0 \leq m \leq n)\)的子集的全集，实际上指的就是组合，故全组合一般都简称为组合。所有组合的个数为\(C_n^m=\frac{n!}{m!(n-m)!}\)。
组合算法实现与全排列算法相似，也分为递归(回溯法)和非递归两种，递归和非递归实现方式这里分别记录若干种方法。
递归实现组合算法
1. 动态规划法
根据组合数的性质可以得到递推式：
\(C^m_n=C^m_{n-1}+C^{m-1}_{n-1}\)
通过以上递推式，我们可以将从\(n\)个元素中任取\(m(m \geq 0)\)个元素的元素规模为\(n\)的组合问题，分解为两个元素规模为\(n-1\)的两个组合子问题，具体算法实现为：
事先在集合的所有\(n\)个元素中确定一个标志元素\(a\)，则两个子问题如下：
- 若元素\(a\)不需要在待求的组合集合中，那么接下来应在原集合剩下的\(n-1\)个元素中任取\(m\)个元素，这个子问题对应递推式中的\(C^m_{n-1}\)；
- 若元素\(a\)需要在待求的组合集合中，那么接下来应在原集合剩下的\(n-1\)个元素中再任取\(m-1\)个元素与标志元素\(a\)组成组合，这个子问题对应递推式中的\(C^{m-1}_{n-1}\)。
对所有的组合问题重复上面的步骤，最后必然会得到两种情况(若最终原集合剩余有\(k(1 \leq k \leq m)\)：
- 剩余的\(k\)个元素全部被选择出来，对应的组合数表达式为\(C^k_k\)；
- 剩余的\(k\)个元素没有一个被选择出来，对应的组合数表达式为\(C^0_k\)。
由此，递归算法的递推形式和终止条件都已知晓，可以根据上述递归算法编写程序求解给定集合的全组合子集。
C++代码实现：
|
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 |
#include<iostream> #include<vector> using namespace std; vector<int> res; //组合结果 (栈存储) int N; //集合元素个数N int M; //取出元素个数M int *a; //集合A (数组存储) void print() { //输出组合子集的结果 for (int i = 0; i < res.size(); ++i) { cout << res[i] << ' '; } cout << endl; } void combination(int k, int m) { //组合递归函数，其中k为标志元素的下标索引，m为待取的元素个数 if (res.size() == M) { //终止条件：取出元素个数达到m个 print(); //输出一种组合结果 } else { if (k < N) { res.push_back(a[k]); //取出标志元素存入栈中 combination(k + 1, m - 1); //取标志元素后，在剩余的n-1个元素中取m-1个元素 res.pop_back(); //标志元素出栈 combination(k + 1, m); //不取标志元素，在剩余的n-1个元素中取m个元素 } } } int main() { cin >> N >> M; //输入N, M a = new int[N]; for (int i = 0; i < N; a[i++] = i ) {} //初始化集合A为1-N的整型数值元素 combination(0, M); //初始标志元素为a[0]，待取元素个数为m个 delete a; return 0; } |
这种求组合的方法体现了动态规划的基本思想，即将原问题分解为相似的子问题，通过迭代求解子问题来得到原问题的解。
2. 顺序法(递归方式)
顺序法是我们平时求解组合时常用的一种方式。实际的思想与上面方法的思想类似。在顺序法中选择元素一般为从左到右依次选择，然后对剩余的元素再重复之前的步骤，直到剩余需要选的元素个数为\(m=1\)，此时遍历取出原集合中剩余的元素与并入到之前已取出的\(m-1\)个元素的子集中，得到组合子集。具体算法实现如下：
- 遍历取出集合中的第\(1\)到第\(n-m+1\)个元素；
- 对于步骤1的所有情况，遍历取出集合剩余元素中的第\(1\)到第\(n-m+2\)个元素；
- 重复步骤2直至需要取的元素个数\(m=1\)，此时遍历取出集合中剩余未被选中的元素并入到之前已取出的\(m-1\)个元素组成的子集中，得到一种组合结果。
C++代码实现：
|
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 34 35 36 37 |
#include<iostream> #include<vector> using namespace std; vector<int> res; //组合结果 (栈存储) int N; //集合元素个数N int M; //取出元素个数M int *a; //集合A (数组存储) void print() { //输出组合子集的结果 for (int i = 0; i < res.size(); ++i) { cout << res[i] << ' '; } cout << endl; } void combination(int k, int m) { if(m == 1) { //终止条件：剩余待取元素个数为1 for(int i = k; i < N; ++i) { //对集合中所有未取的剩余元素进行遍历 res.push_back(a[i]); //遍历取出元素存入栈中 print(); //输出一种组合结果 res.pop_back(); //元素出栈 } } else { for(int i = k; i <= N - m; ++i) { res.push_back(a[i]); //遍历取出元素存入栈中 combination(i + 1, m - 1); //取元素之后，在剩余的n-1个元素中取m-1个元素 res.pop_back(); //元素出栈 } } } int main() { cin >> N >> M; //输入N, M a = new int[N]; for(int i = 0; i < N; a[i++] = i ) {} //初始化集合A为1-N的整型数值元素 combination(0, M); //起始的取出元素为a[0]，待取元素个数为m个 delete a; return 0; } |
非递归实现组合算法
3. 顺序法(非递归方式)
非递归方式的顺序法求解全组合即暴力破解法，对于组合问题中待取出元素的个数\(m\)，利用\(m\)层循环，每一层循环选取一个元素，总共选取所有的\(m\)个元素。这种暴力破解法的缺陷为根据算法得到的程序代码不具有普适性，每一种代码只能对应一个特定的待取出元素的值\(m\)，如果需要更改\(m\)的值，则需要在代码中更改循环嵌套的层数。
例如对于任意元素个数为\(n\)的集合\(A\)，要求取出元素个数为\(3\)的全组合，可以写出如下C++代码：
|
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 |
#include<iostream> #include<vector> using namespace std; vector<int> res; //组合结果 (栈存储) int N; //集合元素个数N (N>=3) int M = 3; //取出元素个数M=3 int *a; //集合A (数组存储) void print() { //输出组合子集的结果 for (int i = 0; i < res.size(); ++i) { cout << res[i] << ' '; } cout << endl; } int main() { cin >> N; //输入N a = new int[N]; for (int i = 0; i < N; a[i++] = i ) {} //初始化集合A为1-N的整型数值元素 for (int i1 = 0; i1 < N - 2; ++i1) { //第一层循环 (取第一个元素) res.push_back(a[i1]); //第一个元素入栈 for (int i2 = i1 + 1; i2 < N - 1; ++i2) { //第二层循环 (取第二个元素) res.push_back(a[i2]); //第二个元素入栈 for (int i3 = i2 + 1; i3 < N; ++i3) { //第三层循环 (取第三个元素) res.push_back(a[i3]); //第三个元素入栈 print(); //输出一种组合结果 res.pop_back(); //第三个元素出栈 } res.pop_back(); //第二个元素出栈 } res.pop_back(); //第一个元素出栈 } delete a; return 0; } |
4. 全排列按位取数法
求组合问题的关键在于找到所有从\(n\)个元素任取\(m\)个元素的全部情况。从\(m\)元素整体的角度考虑可能会使问题变得复杂；但是如果从单个元素的角度考虑问题的话，可以得到一种求解组合问题的另一种思路：
从元素个数为\(n\)集合\(A\)取出\(m\)个元素的得到一个组合子集\(B\)，对于集合\(A\)的任意一个元素\(a_i\)来说，其只存在两种情况：\(a_i \in B\)或者\(a_i \notin B\)。也就是说，对于从集合\(A\)中任取\(m\)得到的任意一种组合情况，都唯一对应着集合\(A\)上所有元素是否属于组合子集\(B\)的一组状态。设定集合\(A\)中的元素属于\(B\)的状态记为\(1\)，元素不属于\(B\)的状态记为\(0\)，在集合\(A\)之外另创建一个长度与集合\(A\)元素个数相同的序列\(C\)来存放集合\(A\)所有元素的状态。此时我们无须关心从集合\(A\)取出元素的顺序等因素，只须关心序列\(C\)的排列情况，序列\(C\)的每一种排列情况与一种组合情况对应，序列\(C\)的全排列对应原问题中的所有组合情况。故我们将一个求集合的组合问题，转化为了一个求序列的全排列的问题。
例如：对于给定的集合\(A=\left\{1,2,3,4\right\}\)，欲求从中任取两个元素得到的全部组合情况，解法如下：
- 先创建一个序列\(C\)保存集合\(A\)所有元素的状态，设定初始状态为取前两个元素得到组合子集\(B\)，即\(C=\left\{1, 1, 0, 0\right\}\)；
- 求序列\(C\)的全排列，便可以得到集合\(A\)中的所有元素的每一种组合情况的状态：
\(1, 1, 0, 0\) 取元素\(1, 2\)
\(1, 0, 1, 0\) 取元素\(1, 3\)
\(1, 0, 0, 1\) 取元素\(1, 4\)
\(0, 1, 1, 0\) 取元素\(2, 3\)
\(0, 1, 0, 1\) 取元素\(2, 4\)
\(0, 0, 1, 1\) 取元素\(3, 4\)
求给定序列的全排列算法在之前已经介绍过，这里不再赘述，由于我们要通过非递归方式求解全组合问题，因此使用的全排列算法为字典序排列算法，具体算法实现如下：
- 创建一个序列\(C\)保存集合\(A\)中元素的状态，不妨设序列\(C\)的前\(m\)个为状态\(1\)，其余为状态\(0\)；
- 利用prev_permutation算法依次求出序列\(C\)的下一个反字典序排列，然后根据求出的排列来遍历集合\(A\)，根据对应的状态来取出相应的\(m\)个元素；
- 重复步骤2直至得到步骤1中序列\(C\)的反向序列为止。
C++代码实现：
|
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 |
#include<iostream> #include<algorithm> #include<vector> #include<string> using namespace std; vector<int> res; //组合结果 (栈存储) int N; //集合元素个数N int M; //取出元素个数M int *a; //集合A (数组存储) string b; //状态标志映射B (字符串存储) void print() { //输出组合子集的结果 for (int i = 0; i < res.size(); ++i) { cout << res[i] << ' '; } cout << endl; } int main() { cin >> N >> M; //输入N, M a = new int[N]; b.append(M, '1').append(N - M, '0'); //前M个状态置1，其余N-M个状态置0 for (int i = 0; i < N; a[i++] = i ) {} //初始化集合A为1-N的整型数值元素 do { for (int i = 0; i < N; ++i) { b[i] == '1' ? res.push_back(a[i]): false; //状态标志为1的元素入栈 } print(); //输出一种组合结果 res.clear(); //清空栈 } while(prev_permutation(b.begin(), b.end())); delete a; return 0; } |
各算法时间消耗
To be continued
Joseph
zwdong