生成组合的算法

win_hate

给定一个 n 个不同元素的集合 A，从中选取 r 个，称为一个 r 组合。所有 r 组合构成的集合记为 C。设法生成 C。

对 n 个元素的 r 排列集合 P 进行分类，若一个排列可以通过若干次对换转成另一排列，则认为这两个排列是等价的。显然，这是 P 上一个等价关系。要生 n 个元素的 r 组合，只要生成等价类的代表元集就行了。

A 有限，总可以设定一个序，不妨假定 a_1<a_2 ...<a_n。把 P 中每一个元素按字典序排列，每个等价类中都有一个最小元，这些最小元的全体就构成了 C。

再按字典序把 C 中的元排个序，则最小为 a_1 a_2 ... a_r, 最大为 a_{n-r+1}...a_{n}，可以设计一个算法从任一个组合 c 得到其后继 c'

若一个组合为: c= (c_1< ...< c_r)， 要得到下一个组合 c'，显然是把 c_r 增大 1。在要得到下一个组合 c''，则把 c_r 再调大 1...

但 c_r 不能一直增大，其上限为 a_n。若 c_r 已经达到上限，则增大 c_{r-1}，同时要把 c_r 调小，使得 c_r,c_{r-1} 为 A 中两个连续的元素. 这样就得到了 c'。若想得到 c' 的后记 c''，则此时有可以把 c_r 调大了。....按此操作，c_{r-1} 不断增大.

但 c_{r-1} 也不能一直增大，其上限为 a_{n-1}，若 c_{r-1} 达到了上限，则调大c_{r-2}, 同时调小 c_{r-1}和 c_{r}，使得 c_{r-2}, c_{r-1}, c_r 是 A 中三个连续的元素。
.....

若 c_1 达到了其上限，表明当前组合为 c 中最大元，没有 c' 了。

上限公式容易写出来， 1<= i<=r 则
r - i <= n - ord(c_i)，有

ord(c_i) <= n-r+i

也即 c_i 之上限为 a_{n-r+i}, 其中 ord(x) 表示 x 在 A 中的序号。

据此不难写出代码，总而言之，就是从右向左找到第一个能增大的元素，增大之，然后它右面的元素尽可能调小。代码见文章末尾：

这里是测试，算一个不太小的，26 取 10:

$ ./a.out 26 10 > log

$ du -h log
139M   log

$ wc -l log
10400600 log

$ cat log | sort| uniq |wc -l
10400600

$ echo 'binomial(26,10);' | maple -q
                                    10400600

代码下载：
http://www.cublog.cn/u/20/upfile/060224143627.gz
我 blog 中对应的帖子
http://www.cublog.cn/u/20/?u=htt ... howart.php?id=78011

[ 本帖最后由 win_hate 于 2006-2-24 14:38 编辑 ]

cjaizss

还没有看你的帖子，我以前的算法是
用n位二进制来模拟幂集中的每个元素，两者是一一对应的。
于是从0遍历到2^n-1,每一位（第m位，不失一般性）的设置与清0意味着幂集中的此元素包含还是未包含原集合中的第m个元素。