《组合数学(第4章4.2).ppt》由会员分享，可在线阅读，更多相关《组合数学(第4章4.2).ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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位二进制数与0到2n1之间十进制数一一对应。
2、生成组合基2算法n初始：an1a1a0000nDo while an1a1a01111）求出使得aj=0的最小整数j2)用1替换aj并用0替换每个aj1,a0。当an1a1a0111时算法结束。n算法按二进制数顺序生成，称为n元组字典序。字典序对应的组合生成n例：集合S=4,3,2,1的组合生成。0000000110010200112,10100301013,101103,201113,2,11000410014,110104,210114,2,111004,311014,3,111104,3,211114,3,2,1n上述生成组合的算法也称为压缩序。n以压缩序生成的相邻组合可能相差较大。是否
3、可以使得相邻的组合尽可能相似？算法2：反射Gray码序生成算法n特点：使得相邻的组合仅相差一个元素仅相差一个元素（增加一个或者删除一个）。n如：n（=1,2,3）元集的组合 n=1,，x0 0 1 n=2,，x0,x0,x1,x1 00 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=3000001101100111011110010n=4,是超立方体n阶Gray反射码的归纳定义1）1阶反射Gray码是 ；2）设n1且n
4、1反射Gray码已经构造；为了构建n阶反射Gray码，首先以n1阶反射Gray码所给出的顺序列出0和1的n1-元组，把0添到每个（n1）元组的开头，然后再反序列出n1阶反射格雷(Gray)码的全部n1元组,并把1加到全部n1元组的开头.n阶反射Gray码以000开始，并以100开始结束，形成循环码。例000111102阶Gray码00011110000011113阶Gray码递归方法构造递归方法构造反射Gray码序生成组合以反射以反射Gray码序生成组合算法码序生成组合算法初始：an1a1a0000nDo while an1a1a01001）计算(an1a1a0)=an1+a1+a02）如果(
5、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个组合是由n-1阶Gray码在开头添加0形成，除第
6、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)是偶数，那么(an2a1a0)是奇数，(bn2b1b0)是偶数，由归纳假设
7、：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