《组合数学第四章》由会员分享，可在线阅读，更多相关《组合数学第四章（12页珍藏版）》请在金锄头文库上搜索。
1、组合数学第四章 生成排列和组合主要内容： 1. 生成排列的邻位互换法 2. 生成排列的逆序数法 3. 生成组合的字典序法 4. n阶Gray码 要点: 生成算法和序号邻位互换法(p54-58)引子: 字典序法(例: 123456, 245136) 要点: 每次只交换两个相邻数遍历所有排列 且 不重复 步骤: 先找到合适的次序, 再实现它 方案: 假设k=n-1阶的次序已经设计好n在n-1阶排列上穿插可得n阶的次序 分析: 相邻两排列只有邻位互换无重复 无遗漏 能否先给出一个递归算法?递归算法(补充)初始: 排列为12n, 每个数的方向都向左.1,2,k的邻位互换程序LH(k):若 k的方向侧邻
2、居ak的数的方向. 若还有活动数, 转2.注: (1) 编程时可进一步改进.(2) 可以直接计算每个排列的序号.(p58) 例: 计算25143的序号.排列与逆序列(p58-61)设i1in是1,n的一个全排列 令aj是j的左边大于j的数的个数, 则称a1an是i1in的逆序列. 注:an=0. 例: 31524的逆序列是12010 还原逆序列:1. 从大到小还原, 2. 从小到大还原 逆序列的生成, 计算逆序数的算法生成全体组合(p62-64)S=xn-1,x1,x0, AS, A an-1a1a0, 若 xi A, 则 ai = 1, 否则则 ai = 0. 称为为n元组组的字典序. 缺点
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 n阶Gray码(p65-68)定义: n阶Gray码是n元组的一个列表,相邻两组合只相差一个元素. n阶反射Gray码的归纳定义: (1) 1阶Gray码是 0, 1; (2) 设n1, 且n-1阶Gray码已定义好,将n-1阶Gray码顺序列一遍, 接下来将n-1阶Gray码反序列一遍,顺序列的码每个前面添0,反序列的码每个前面添1.生成n阶反射Gray码的算法(p68-69)(1) 从an
4、-1a1a0=000开始 (2) 当an-1a1a0100时时,i) 计计算 = an-1+a0 (1的个数),ii) 若偶, 则则 a0 a0,iii) 若奇, 则则找 j 0 使得ajaj-1a0=100, 执执行 aj+1 aj+1. 例:10111100, 0001111 的后继继, 前驱驱. 定理: 上述算法产产生n阶阶Gray码码. 证证明: 数学归纳归纳 法.生成S=1,2,n的r组合(p69-72)i1,irS表示为i1ir (i1ir) 字典序: 将组合作为r位数来看得到的顺序 问题: 生成, 序号, 例: n=9, 13589 特点: k ik n-r+k (1) 从i1ir=12r (2) 找最大的使得 ik n-r+k 的数k (3) 用i1ik-1(ik+1)(ik+r-k+1)替换i1ir. 定理: 在S的所有r组合中, i1ir的序号是本章小结与作业排列的邻位互换生成法 排列的逆序列 排列和组合的字典序法 组合的Gray反射码 r-组合的字典序法 作业: 第四章 ex7,ex15, ex24, ex33, ex52. 思考题: ex25.二项式定理(p81, p84)Pascal公式 二项式定理(the binomial theorem) 一些恒等式(p87, p89)
