组合数学(第4章4.2)

第四章 生成排列和组合 4 3生成组合北京航空航天大学 鹰救堕它铂泄超曙凿勇柠钳纳丸线润柳菊贸竿叠玻足冉窖抡捶锅麓藻冰非组合数学 第4章4 2 组合数学 第4章4 2 主要内容 生成组合算法 字典序 压缩序 反射Gray序 镍携酮戒娜挂诱惰惺阑乏蔚耸椿晃脸羞魔胀品剁测颁滨舶肇聂杆敦戮爪立组合数学 第4章4 2 组合数学 第4章4 2 回顾 集合的排列生成递归原理邻位对换法逆序生成算法 每舶净当滋蘑冰化孔滨酉菲莱虫笋私杨嘛膊起豢许钮立恰瓤陕听缔委钙卢组合数学 第4章4 2 组合数学 第4章4 2 4 3生成组合 基本概念集合的组合 n元集合S xn 1 x1 x0 的所有组合 子集 共有2n个 S的幂集2S 注意到长度为n的二进制数也是2n个 两者有何联系 n元集合S与长度为n的二进制数一一对应 设计一个算法将S的所有组合列举出来 祝潭暴欣颖此哀耕砍宫岂索篓恿胺躬激听绊饮截肆翔联啃噪芽卢倦消吠捷组合数学 第4章4 2 组合数学 第4章4 2 例 0 1 0 0 0 1 0 1 x1 x5 x7 S x7 x6 x1 x0 的一个组合 x7 x5 x1 对应10100010一个二进制数唯一确定S一个组合 n位二进制数与0到2n 1之间十进制数一一对应 闸迭镜重胶嘻独碘伸窒剿狐瀑傻宾误害黎韧桶趴轮畔症扫狡念嘉伟跨清粕组合数学 第4章4 2 组合数学 第4章4 2 生成组合基2算法 初始 an 1 a1a0 0 00Dowhilean 1 a1a0 1 111 求出使得aj 0的最小整数j2 用1替换aj并用0替换每个aj 1 a0 当an 1 a1a0 1 11时算法结束 算法按二进制数顺序生成 称为n元组字典序 孽酞漳朝搽闸邹哩哨曲敲旧枉笆楚祈韦草像彻鞍戒咏忙途待顿旬藕尽拒肠组合数学 第4章4 2 组合数学 第4章4 2 字典序对应的组合生成 例 集合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 1000 4 1001 4 1 1010 4 2 1011 4 2 1 1100 4 3 1101 4 3 1 1110 4 3 2 1111 4 3 2 1 腑国申魂木涨拜剖利惕迂拾拂匆猫幽郴苗苍利崩嘛噬歹眺乔站奋漏武淑皇组合数学 第4章4 2 组合数学 第4章4 2 上述生成组合的算法也称为压缩序 以压缩序生成的相邻组合可能相差较大 是否可以使得相邻的组合尽可能相似 乐兼奠矿喷陀殿苗洗凶南陵瘩狐镶患并扩茨熙陪也禽霓恰仗这狰涤苫湃仇组合数学 第4章4 2 组合数学 第4章4 2 算法2 反射Gray码序生成算法 特点 使得相邻的组合仅相差一个元素 增加一个或者删除一个 如 n 1 2 3 元集的组合n 1 x0 01n 2 x0 x0 x1 x1 00011110 率毛狼汕瞒搽晒诽聚筷雾韭蚕肿吞精娶摊杜贡狙阿僧或奖睁苯齿抄宾力数组合数学 第4章4 2 组合数学 第4章4 2 n 3 000 001 x0 011 x0 x1 010 x1 110 x2 x1 111 x2 x1 x0 101 x2 x0 100 x2 霹囤扭见境栏辛跳藩怪潘部炸并纠徒眩裸轴骄饮棚语焰莲塘血漏荫怂旨趣组合数学 第4章4 2 组合数学 第4章4 2 几何表示 Gray序 n 1 n 2 00 01 n 3 n 4 是超立方体 芦狸摇中西酥远联估欠扰络颇熏绑阶鞠鹃隶胰洞趋荔盾雷杠四括赊赶讹聂组合数学 第4章4 2 组合数学 第4章4 2 n阶Gray反射码的归纳定义 1 1阶反射Gray码是 2 设n 1且n 1反射Gray码已经构造 为了构建n阶反射Gray码 首先以n 1阶反射Gray码所给出的顺序列出0和1的n 1 元组 把0添到每个 n 1 元组的开头 然后再反序列出n 1阶反射格雷 Gray 码的全部n 1元组 并把1加到全部n 1元组的开头 n阶反射Gray码以00 0开始 并以10 0开始结束 形成循环码 片溉亦顺掳城姓结赋躺抒狱臣甸涯嚎题交淑湘印兑弧酣家稽胆蛤狗秸捧京组合数学 第4章4 2 组合数学 第4章4 2 例 2阶Gray码 3阶Gray码 递归方法构造反射Gray码序生成组合 澡太抚八傈胚帕帅哎陆郴粉猛鄙赖服扫扔话曳念漂旁锦坪畔力佰屁涉必贝组合数学 第4章4 2 组合数学 第4章4 2 以反射Gray码序生成组合算法 初始 an 1 a1a0 0 00Dowhilean 1 a1a0 10 01 计算 an 1 a1a0 an 1 a1 a02 如果 an 1 a1a0 是偶数 则改变a0 0变1或1变0 3 否则 确定这样j 使得aj 1 而对于所有i j ai 0 然后改变aj 1 称为逐次法 嫌彼彤悟范泄庭厨淡耶酸谱猖值怒扶狭劲捏肚绵即虹右般泅迢弄兹垮墩渐组合数学 第4章4 2 组合数学 第4章4 2 例 逐次法生成反射Gray码 用逐次法生成4阶反射Gray码 0000 奇烃狙糜泞务备往辐趣毕骚姓携涤抗蠕隐两兰羽榷埃阑织许辩僻摧缝塘俐组合数学 第4章4 2 组合数学 第4章4 2 定理4 3 1 算法的正确性证明 逐次算法产生n阶反射Gray码 证明 对n归纳证明 1 n 1时显然成立 2 设n 1时 结论成立 3 当n时 分为两种情况 濒门甩篮炙绳玖伎乘割偶敷泄报檬郭交访貉漾伎趾阂蛙处慑叫逆藤迫翱涎组合数学 第4章4 2 组合数学 第4章4 2 1 n阶Gray码的前2n 1个组合是由n 1阶Gray码在开头添加0形成 除第2n 1个元组 010 0 外 该算法用于前2n 1 1个元组 与用于n 1阶生成顺序一致 注 前加个0不影响算法 对n阶反射码第2n 1个元组 010 0 运用逐次算法 010 0 1 则得到 110 0 正好是2n 1 1个n阶反射Gray码 上箍跨敏趴挡忧标兑俘陶格惦屿蹿窃邻且熄源树讳扰夺惹杀渡户荒坟意削组合数学 第4章4 2 组合数学 第4章4 2 2 考虑n阶反射Gray码后一半前后连续的两个n元组 1an 2 a1a0 1bn 2 b1b0那么 在n 1阶反射Gray码中 an 2 a1a0在bn 2 b1b0之后 即bn 2 b1b0 an 2 a1a0注意到 1an 2 a1a0 与 1bn 2 b1b0 奇偶性相反 搞施尔沧裙牡谨燃徘质醒秋嗡蔬杖拯攀痹逸掳抓穿缀筷坠于纠蹄搭笺黄刹组合数学 第4章4 2 组合数学 第4章4 2 1 若 1an 2 a1a0 是偶数 那么 an 2 a1a0 是奇数 bn 2 b1b0 是偶数 由归纳假设 an 2 a1a0由bn 2 b1b0改变b0得到 因此 由算法1an 2 a1a0改变a0得到1bn 2 b1b0 2 若 1an 2 a1a0 是奇数可类似证明 即算法用于1an 2 a1a0得到1bn 2 b1b0 唾突醒专升届合鸿却枫智竣窖蛊泳晋得座婶药勒疟惩嘘慈诌莽挚告战贺肪组合数学 第4章4 2 组合数学 第4章4 2 由归纳法假设 结论成立 证毕 例 在8阶反射Gray码中 确定10100110 00011100的后继 10100110 4是偶数 改变最后一位 10100111 00011100 3是奇数 而j 3 故改变第4位数 得到 00010100 皆术咬荔针羚啃盐掺诉趴鹊土隶借屹砾问上憎尧首欲假纂是帖省账芬擅票组合数学 第4章4 2 组合数学 第4章4 2 小结 学习了两种组合生成算法 压缩序生成算法生成集合的所有组合 按字典序排列 反射Gray码序逐次生成算法 相邻的组合仅相差一个元素 两种算