1、第四章 生成排列和组合4.3 生成组合令 n个元素的集合 S=xn-1,xn-2,x 1,x0。我们寻找一种生成 S的所有组合（或者说子集）的算法，算法的结果应该仅仅是 S的 组合 。由前面的知识，我们可以分别从 S取出0,1,2,.n个元素来构造子集合的个数共计有：1给定 S的一个组合 A, 当 A= n 时， A= S ; 当A n时， 组合 A中不包含 S的所有元素，则 S的每一个元素 xi或者属于 A或者不属于 A， 如果用 1表示是属于 A， 用 0表示不属于 A， 那么就能用 2n个字符 组合成长度为 n的 1和 0的 n元组：(an-1, an-2, a1, a0) = an-1
2、 an-2, a1 a0 (ai =0,1 ) 来区分集合 S的 2n个组合 (子集 )。对于每个i=0,1,. n-1, 令 n元组的第 ai 项对应于元素 xi 。2例 : 当 n = 3 时， 23 = 8 个组合以及它们对应的 3元组如下： 组 合 序列 a2 a1 a0 0 0 0 x0 0 0 1 x1 0 1 0 x1, x0 0 1 1 x2 1 0 0 x2, x0 1 0 1 x2, x1 1 1 0 x2, x1, x0 1 1 1可以看出：组合 中有哪个元素，在序列 相应位置上就有个 1 ； 第一列相当于集合 x2, x1, x0 的幂集。3例 :令 S=x6,x5,x
3、4,x3,x2,x1,x0. S的 组合 x5,x4,x2,x0是 个中的一个，对应的 7元组是 :0110101;同样 7元组 1010001对应的组合是： x6, x4, x0由于 n个元素的组合可以用 0和 1的 n元组确定，为了生成 n个元素的集合的所有组合，只要能够以表的形式写出 0和 1的 2n个 n元组的系统的过程就足够了。现在每一个 n元组都可以看成是基础为 2的一个数（二进制记数）。4例： 10011是整数 19的二进制数，因为：19 = 124 + 023+022+1 21 + 120一般地，给定一个从 0到 2n-1的 整数 m , 则数 m可以由如下形式表示：m = a
4、n-1 2n-1 + an-1 2n-2 + a1 21 + a0 20 其中每个 ai 是 0和 1，反之亦然。因此， 0和 1的 n元组与 整数 0,1,2,. 2 n-1之间存在一一对应。 5于是生成 S xn-1,xn-2,x 1,x0的 2n个组合的问题就转化成生成 2n个 n位二进制数的问题。现在就变的简单了： 以由小到大的顺序写出从 0到 2n-1的 数，但要转化成二进制形式，使用基为 2的运算每次加 1递增。例 :令 n = 7。 数 29在 0和 27-1之间并且可以表示成29 = 026 +025 +124+123+122+0 21 + 1206因此， 29有 一个由 00
5、11101给出的 7位数字的二进制表示并且对应集合：S x6, x5, x4 , x3, x2, x1, x0的 一个组合：x4 , x3, x2, x0； 同样可以求出整数 29在 0和 25-1之间的二进制表示和对应的 5元组如下：29 = 025 +124+123+122+0 21 + 120与基 2数 11101 和组合 x4 , x3, x2, x0对应。7生成 S=xn-1,xn-2,x 1,x0的 2n个组合，或者 说生成 0和 1的 2n个 n元组，只要用二进制形式， 使用基为 2的运算每次加 1，再按由小到大顺序写出从 0到 2n 1的 数，使他们一一对应。组合序列 基为 2
6、的 n元组 0到 2n 1的整数例：生成 0和 1的 4元组；解： 4元组共有 24=16个数， 如下表：80 0 0 0 0 8 1 0 0 01 0 0 0 1 9 1 0 0 12 0 0 1 0 10 1 0 1 03 0 0 1 1 11 1 0 1 14 0 1 0 0 12 1 1 0 05 0 1 0 1 13 1 1 0 16 0 1 1 0 14 1 1 1 07 0 1 1 1 15 1 1 1 19例：紧接集合 S x6, x5, x4 , x3, x2, x1, x0的一个组合 x6, x4 , x2, x1, x0后面的组合是什么？解：组合 x6, x4 , x2, x1, x0对应的二进制数是：1010111。用基为 2的运算，下一个组合应该对应： 1010111+ 11011000此二进制数对应的组合是： x6, x4 , x310
