Combination - 组合

问题

从包含 $n$ 个元素的集合 $s = [x_0, x_1, x_2, \dots ,x_{n-1} ]$ 中任意取 $m$ 个元素（ $m \leq n$ ）组成组合，求所有组合。集合 $s$ 中任意两元素互不相同。

解法

设置集合 $c = [ c_0, c_1, c_2, \dots , c_{m-1} ]$ 表示集合 $s$ 的选择， $c_i = 1$ 表示选择数字 $x_i$ ， $c_i = 0$ 表示不选择数字 $x_i$ 。比如集合 $s = [ x_0, x_1, x_2, \dots, x_{n-1} ]$ 中取出组合

$[x_0, x_1, x_2]$

等价于集合

$c = [1_0, 1_1, 1_2, 0_3, \dots, 0_{n-1} ]$

即元素 $[ c_0, c_1, c_2 ]$ 为 $1$ ，元素 $[ c_3, \dots, c_{n-1} ]$ 为 $0$ 。

可以看出，包含 $n$ 个元素的集合 $s = [x_0, x_1, x_2, \dots, x_{n-1} ]$ 中取出 $m$ 个元素的所有组合，可以转化为求有 $i$ 个 $1$ ， $m - i$ 个 $0$ 的集合 $c$ 的唯一全排列，其中 $0 \leq i \leq m$ 。

$(1)$ 从集合 $s$ 中取出 $0$ 个元素作为组合，即 $c$ 中有 $0$ 个 $1$ ， $m$ 个 $0$ ，唯一全排列有 $C_0^m = 1$ 个

$[]$

$(2)$ 从集合 $s$ 中取出 $1$ 个元素作为组合。则 $c$ 中有 $1$ 个 $1$ ， $m-1$ 个 $0$ ，唯一全排列有 $C_1^m = m$ 个

$\begin{array}{lcr} [ 1_0, 0_1, 0_2, \dots , 0_{n-1} ] \\ [ 0_0, 1_1, 0_2, \dots , 0_{n-1} ] \\ [ 0_0, 0_1, 1_2, \dots , 0_{n-1} ] \\ \cdots \\ [ 0_0, 0_1, 0_2, \dots , 1_{n-1} ] \end{array}$

$(3)$ 从集合 $s$ 中取出 $2$ 个元素作为组合，则 $c$ 中有 $2$ 个 $1$ ， $m-2$ 个 $0$ ，唯一全排列有 $C_2^m = m$ 个。

只要求出所有唯一全排列，即可反向求出对应的组合。

包含 $n$ 个元素中选出 $m$ 个元素的所有组合，需要重复 $m + 1$ 次，每次求有 $i$ 个 $1$ ， $m - i$ 个 $0$ 的集合 $c$ 的唯一全排列，其中 $i \in [0, m]$ 。根据全排列反向得到组合，算法结束。第 $i$ 步求唯一全排列的时间复杂度为 $O(i!)$ ，该算法的时间复杂度为 $O(C_m^n) = O(\frac{n!}{m! \cdot (n-m)!})$ 。

StackOverflow - algorithm-to-return-all-combinations-of-k-elements-from-n

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

二项式系数

https://en.wikipedia.org/wiki/Binomial_coefficient

Chase’s Twiddle - Algorithm 382: Combinations of M out of N Objects:

Buckles - Algorithm 515: Generation of a Vector from the Lexicographical Index:

Remark on algorithm 515: Generation of a vector from the lexicographical index combinations

http://dl.acm.org/citation.cfm?id=1236470

源码

Combination.h

Combination.cpp

测试

CombinationTest.cpp