组合数学(第4章4.2).ppt

1、第四章：生成排列组合，4.3生成组合，北航大学，主要内容，生成字典顺序(压缩顺序)反映组合算法的灰度顺序，复习，集合的排列生成递归原理，相邻排列方法和逆序生成算法，4.3生成组合，组合n元集合sxn1，x1和x0的组合有2n个组合(子集)的基本概念集。(发电机组2S)。请注意，还有2n个长度为n的二进制数。它们之间有什么关系？n元集s与长度为n的二进制数一一对应。设计一个算法来列出s的所有组合。例如：0、1、0、0、1、0、1、1、x1、x5、x7、sx7、X6、x1、x0、x7、X5、x1的组合对应于1010010位二进制数对应于0到2n1之间的十进制数。生成组合基2算法，最初：an1a1a

2、0000 Do，而an1a1a0111 1)查找使aj=0的最小整数j 2)用1替换aj，并用0替换每个aj1、a0。当出现1a1a0111时，算法结束。该算法是以二进制数的顺序生成的，这种顺序称为N元组字典顺序。字典顺序对应的组合生成，例如：集合S=4，3，2，1。0000、0001、1、0010、2、0011、2、1、0100、3、0101、3、1、0110、3、2、0111、3、2、1、100按压缩顺序生成的相邻组合可能会有很大不同。相邻的组合能尽可能相似吗？算法2:反射格雷码序列生成算法，其特征在于使相邻组合仅相差一个元素(增加一个或删除一个)。例如，n(=1，2，3)个元素集的组合n

3、=1，x0 0 1 n=2，x0，x0，x1，x1 0001110，n=3，000，001x0，011x0，x1 010 x 1，110x2，x1。几何表示(灰度级)，n=1，n=2，00，01，n=3，n=4，是超立方体，n，1级灰度反射码的归纳定义。2)让n1和n1反映已经构造的格雷码；为了构造N阶反射格雷码，首先按照n1阶反射格雷码给出的顺序列出0和1的n1元组，然后以相反的顺序列出n1阶反射格雷码的所有n1元组，并在所有n1元组的开头加上1。N阶反射格雷码以000开始，以100结束，形成循环码。例如，二阶格雷码，三阶格雷码，递归方法构造反射格雷码序列生成组合ij，ai0反射格雷码序列生

4、成组合算法，最初：当an1a01001)计算(an1a0a0)=an 1a 02)如果(an 1a 0a 0)是偶数，则改变a0(0到1或1到0)示例：反射格雷码通过连续方法生成，而四阶反射格雷码通过连续方法生成。0000，定理4.3.1:算法的正确性证明了逐次算法产生了N阶反射格雷码。证明：n. 1的归纳证明。n=1显然是正确的。2.当n1被设置时，结论成立。3.当N为0时，有两种情况：(1)N阶格雷码的前2n-1个组合是在n-1阶格雷码的开头加0形成的。除了第2n-1个元组(0100)，该算法用于第2n-11个元组，其顺序与用于n-1顺序生成的顺序相同(注意：之前添加0不会影响该算法)。对

5、于第2n-1个元组(0100)的N阶反射码，使用连续算法：(0100)1，然后(1100)正好是第2n-1个N阶反射格雷码。(2)考虑在n阶反射格雷码的后半部分之前和之后连续的两个n元组：1an2a101bn2b1b0。然后，在n-1阶反射格雷码中：an2a1a0在bn2b1b0之后，即，bn 2b 0 an2a 10注意到(1an2a10)和(1bn2b1b0)具有相反的奇偶性。1)如果(1an2a1a0)是偶数，那么(an2a1a0)是奇数，而(bn2b1b0)是偶数，这是通过归纳假设an2a1a0从bn2b1b0变为b0而获得的，因此通过算法1an2a10改变a0而获得1bn2b1b0。2)如果(1an2a1a0)是奇数，则可以类似地证明。也就是说，将该算法应用于1an2a1a0以获得1bn2b1b0。由归纳假设，结论成立。证书已完成。例如：在8阶反射格雷码中，确定10100110，00011100的后继。(10100110)=4是偶数，更改最后一位：10100111；(00011100)=3是一个奇数，j=3，因此将第4位数字改为：00010100。综上所述，本文研究了两种组合生成算法：压缩顺序生成算法生成所有以字典顺序排列的集合组合