1 介绍

排列（Permutation）和组合（Combination）是两个基础的数学概念。

计算排列与组合可以解决一些实际的工程问题，掌握排列组合计算的方法是十分重要的。

目前，网上已经有一些计算排列组合的算法，比如[1]。

这里我也给出一个组合计算方法。该计算方法采用了分治的思想，代码实现采用了递归的方式。

2 组合算法

2.1 设计思路

组合问题：在序列An={1,2,3,4,5,6,...,n}中选择m个数一共有C(n,m)种组合，求解所有的组合。

例如，C(3,2)=3. 所有的组合分别是{1,2},{1,3},{2,3}。

思路：

我的算法采用了分治的思想：将一个大的问题拆分成很多个子问题，先解决子问题，所有子问题的解共同组成了大问题的解。

接下来我以求组合C(5,3)为例进行说明：

假设C(5,3)的所有组合形成的集合是E。我们可以将组合结果E分成两类：A类是含有5的组合，B类是不含5的组合；

同理，我们可以将B类分成B1和B2两类：B1类是含有4的组合（且不含5的组合），B2类是不含4的组合（且不含5的组合）；

同理，我们可以将B2类分成B21和B22两类：B21类是含有3的组合（且不含5、4的组合），B22类是不含3的组合（且不含5、4的组合）。注意，此时B22类是不成立的（应为不含3、4、5，只剩下1、2两个元素。而例子要求解C(5,3)至少需要3个元素）。

以上分类方法可以保证E=B21 U B1 U A

其中，

对于A类组合，我们只需要求解子问题C(4,2)，之后再在子问题的结果中加入5即可得到A类组合；

对于B1类组合，我们只需要求解子问题C(3,2)，之后再在子问题的结果中加入4即可得到B1类组合；

对于B21类组合，我们只需要求解子问题C(2,2)，之后再在子问题的结果中加入3即可得到B21类组合；

A类组合、B1类组合、B21类组合组成了C(5,3)的所有组合。

可以发现，问题C(5,3)已经降维成三个子问题：C(4,2)，C(3,2) 和C(2,2)。利用递归的方法即可实现最终结果的求解。

2.2 算法复杂度

2.2.1 时间复杂度

所有的组合算法的时间复杂度都至少是C(n,m)=n!/[m!*(n-m!)]。本算法的时间复杂度也是阶乘量级的。

2.2.2 空间复杂度

由于采用了递归的实现方式，本算法的空间复杂度很高，很有可能造成内存溢出。建议采用非递归的方法实现组合计算。

2.3 源代码

下面是源代码：

/*****************************************************************************************************************************时间复杂度：空间复杂度：功能：求排列组合Cij输入参数：int i                :        总数int j                :          组合数vector<int>r:        用于存储临时结果的向量，大小必须等于num int num                :        组合数vector<vector<int> > & result        :        用于存储最终所有结果的二维向量 返回参数：void注意：　首先建立两个向量作为函数的输入参数                vector<int> r(num);                                //num为组合数 vector<vector<int> > result;        //存储最终结果 使用样例：vector<int> resulttemp(3);vector<vector<int> > result;Cij(6,3,resulttemp,3,result); 
*****************************************************************************************************************************/void Cij(int i, int j,vector<int> &r,int num,vector<vector<int> > & result)
{//排列组合公式Cij//cout << n << ' ' << i << ' ' << j << endl;if (j == 1){for (int k = 0; k < i; k++){vector<int> temp(num);r[num - 1] = k;for (int i = 0; i < num;i++){temp[i]=r[i];//cout << r[i] << ' ';}result.push_back(temp);//cout << endl;}}else if (j == 0){//do nothing!}else{for (int k = i; k >= j; k--){r[j-2] = k-1;Cij(k - 1, j - 1,r,num,result);}}
}