《组合数学(第4章4.2)》由会员分享，可在线阅读，更多相关《组合数学(第4章4.2)（22页珍藏版）》请在金锄头文库上搜索。
1、第四章：生成排列和组合4.3 生成组合北京航空航天大学主要内容n生成组合算法 字典序(压缩序) 反射Gray序 回顾n集合的排列生成n递归原理n邻位对换法n逆序生成算法4.3 生成组合n基本概念n集合的组合 n元集合Sxn1, , x1, x0的所有组合（子 集）共有2n个。（S的幂集2S）。 注意到长度为n的二进制数也是2n个，两者 有何联系？ n元集合S与长度为n的二进制数一一对应。n设计一个算法将S的所有组合列举出来 。例：01000101x1x5x7 Sx7, x6, , x1, x0的一个组合x7, x5, x1对应 10100010 一个二进制数唯一确定S一个组合。 n位二进制数与
2、0到2n1之间十进制数一一对应。生成组合基2算法n初始： an1a1a0000nDo while an1a1a01111）求出使得aj=0的最小整数j2) 用1替换aj并用0替换每个aj1,a0。当an1a1a0111时算法结束。n算法按二进制数顺序生成，称为n元组字典序。字典序对应的组合生成n例：集合S=4,3,2,1的组合生成。00000001100102 00112,1 01003 01013,1 01103,2 01113,2,11000410014,1 10104,2 10114,2,1 11004,3 11014,3,1 11104,3,2 11114,3,2,1n上述生成组合的算
3、法也称为压缩序。n以压缩序生成的相邻组合可能相差较大 。是否可以使得相邻的组合尽可能相似 ？算法2：反射Gray码序生成算法n特点：使得相邻的组合仅相差一个元素 （增加一个或者删除一个）。n如：n（=1,2,3）元集的组合n=1, ，x00 1n=2, ，x0, x0, x1, x100 0 1 1 1 1 0nn=3000 001 x0 011 x0 , x1 010 x1 110 x2, x1 111 x2, x1, x0 101 x2, x0 100 x2 几何表示（Gray序）n=101n=200011110n=3000001101100111 011110010n=4,是超立方体n阶
4、Gray反射码的归纳定义1）1阶反射Gray码是 ； 2）设n1且n1反射Gray码已经构造；为了构 建n阶反射Gray码，首先以n1阶反射Gray码 所给出的顺序列出0和1的n1-元组，把0添到 每个（n1）元组的开头，然后再反序列出 n1阶反射格雷(Gray)码的全部n1元组, 并把 1加到全部n1元组的开头.n阶反射Gray码以000开始，并以100开始 结束，形成循环码。例000111 102阶Gray码00011110000 0111 13阶Gray码递归方法构造反射Gray码序生成组合以反射Gray码序生成组合算法初始：an1a1a0000nDo while an1a1a0100
5、1）计算(an1a1a0)= an1+a1+a0 2）如果(an1a1a0)是偶数，则改变a0（0 变1或1变0）3）否则，确定这样j，使得aj1，而对于所 有ij, ai0，然后改变aj+1.称为逐次法。例：逐次法生成反射Gray码n用逐次法生成4阶反射Gray码。0000000100110010011001110101010011001101111111101010101110011000定理4.3.1: 算法的正确性证明n逐次算法产生n阶反射Gray码。 证明：对n归纳证明。1. n=1时显然成立。2. 设n1时，结论成立。3. 当n时， 分为两种情况：（1）n阶Gray码的前2n-1个
6、组合是由n-1阶Gray 码在开头添加0形成，除第2n-1个元组（ 0100）外，该算法用于前2n-11个元组，与 用于n-1阶生成顺序一致(注：前加个0不影响 算法)。对n阶反射码第2n-1个元组(0100) ，运用逐次算法：(0100)1，则得 到(1100)正好是2n-1+1个n阶反射Gray 码。（2）考虑n阶反射Gray码后一半前后连 续的两个n元组：1an2a1a0 1bn2b1b0那么，在n-1阶反射Gray码中： an2a1a0在bn2b1b0之后，即 bn2b1b0 an2a1a0 注意到(1an2a1a0)与(1bn2b1b0)奇 偶性相反。1) 若(1an2a1a0)是偶
7、数，那么 (an2a1a0)是奇数， (bn2b1b0) 是偶数，由归纳假设： an2a1a0由 bn2b1b0改变b0得到，因此，由算法 1an2a1a0改变a0得到1bn2b1b0。2) 若(1an2a1a0)是奇数可类似证明 。即算法用于1an2a1a0得到 1bn2b1b0 。由归纳法假设，结论成立。证毕。例：在8阶反射Gray码中, 确定10100110， 00011100的后继. (10100110)=4是偶数，改变最后一位：10100111 ； (00011100)=3是奇数，而j=3，故改变第4位数， 得到： 00010100。小结n学习了两种组合生成算法：n压缩序生成算法生成集合的所有组合，按 字典序排列。n反射Gray码序逐次生成算法。相邻的组合 仅相差一个元素。n两种算法均无需存储先前组合，具有各 自特点，可用于解决不同问题。作业n4.6 练习题 11，12，13，17，18，23
