组合_chapt4_16生成排列与组合.pptx

组合数学第四章 生成排列和组合主要内容：1. 生成排列的邻位互换法2. 生成排列的逆序数法3. 生成组合的字典序法4. n阶Gray码要点: 生成算法和序号邻位互换法(p53-57)引子: 字典序法(例: 123456, 245136)要点: 每次只交换两个相邻数 遍历所有排列 且 不重复步骤: 先找到合适的次序, 再实现它方案: 假设k=n-1阶的次序已经设计好 n在n-1阶排列上穿插可得n阶的次序 分析: 相邻两排列邻位互换, 无重复, 无遗漏 计算25143的序号? 算法?n的移动(补充)初始: 排列为12…n, 每个数的方向都向左. {1,2,…,n}的邻位互换程序LH(n): 若 n的方向侧有邻居a, 则 a n 互换, 返回; 否则 执行LH(n-1), n的方向反向, 返回.递归算法(补充)初始: 排列为12…n, 每个数的方向都向左. {1,2,…,n}的邻位互换程序LH(k): 若 k的方向侧邻居ak, 则 a k 互换, 返回; 否则 执行LH(k-1), k的方向反向, 返回.定义: 若数k方向侧邻居ak, 则称k为活动数. 去掉递归: 找最大的活动数, 移动k后, 比k大的都反向去掉递归的邻位互换算法(p56)1. 初始排列为12…n, 每个数的方向都向左.2. 对于最大的活动数k, 交换k与其方向的邻居, 改变所有k的数的方向. 若还有活动数, 转2.注: (1) 编程可改进. (2) 计算25143的序号(从0开始 ).(p57) 排列序号奇偶10偶210?2+1=1奇2131?3+2=5奇21435?4+2=22偶2514322?5+3=113奇排列与逆序列(p57-60)设i1…in是{1,…,n}的一个全排列令aj是j的左边大于j的数的个数, 则称a1…an是i1…in的逆序列.注:an=0, 0?aj?n-j例: 31524的逆序列是12010还原逆序列: 1. 从大到小还原, 2. 从小到大还原 生成逆序列, 计算逆序数的算法逆序列的序号(补充)长度序列逆序列序号4123400000124300101132401002=1?2+0142301103=1?2+1134202004=2?2+0143202105=2?2+1213410006=1?2?3+0214310107=1?2?3+14321321023=3?2?3 +2?2+110123457(10)896000004011099=4?2?3?4+1?2+1生成全体组合(p60-63)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 S={xn-1,…,x1,x0}, A?S, A ? an-1…a1a0,若 xi ? A, 则 ai = 1, 否则 ai = 0.称为n元组的字典序.缺点:每次变多个元素n阶Gray码(p65)11111011101011000110100001000001定义: n阶格雷(Gray)码是n元组的一个列表, 相邻两组合只相差一个元素.超立方体(hypercube)000-100-101-111-110-010-011-001n阶反射Gray码(p65-67)n阶反射Gray码的归纳定义:(1) 1阶反射Gray码是 0, 1;(2) 设n1, 且n-1阶反射Gray码已定义好, 将n-1阶码顺序排列一遍, 接下来 将n-1阶码反序排列一遍, 顺序排列的码每个前面添0, 反序排列的码每个前面添1.生成n阶反射Gray码的算法(p66-67)(1) 从an-1…a1a0=0…00开始(2) 当an-1…a1a0?10…0时, i) 计算? = an-1+…+a0 (1的个数), ii) 若?偶, 则 a0 ? ?a0, iii) 若?奇, 则找 j ? 0 使得ajaj-1…a0=10…0, 执行 aj+1 ? ?aj+1.例 0001111 的后继, 前驱. 定理: 上述算法产生n阶Gray码. 数学归纳法 /view/6c9501afd1f34693daef3e85.html/view/6c9501afd1f34693daef3e85.html, /blog/static/71568133200910813518302//blog/static/71568133200910813518302/ 生成S={1,2,…,n}的r组合(p67-70){i1,…,ir}?S表示为i1…ir (i1…ir)字典序: 将组合作为r位数来看得到的顺序 问题: 生成,