组合数学第四章精品文稿.ppt

组合数学第四章第1页，本讲稿共12页邻位互换法邻位互换法(p54-58)引子引子:字典序法字典序法(例例:123456,245136)要点要点:每次只交换两个相邻数每次只交换两个相邻数 遍历所有排列遍历所有排列 且且 不重复不重复步骤步骤:先找到合适的次序先找到合适的次序,再实现它再实现它方案方案:假设假设k=n-1阶的次序已经设计好阶的次序已经设计好 n在在n-1阶排列上穿插可得阶排列上穿插可得n阶的次序阶的次序分析分析:相邻两排列只有邻位互换相邻两排列只有邻位互换 无重复无重复 无遗漏无遗漏能否先给出一个递归算法能否先给出一个递归算法?第2页，本讲稿共12页递归算法递归算法(补充补充)初始初始:排列为排列为12n,每个数的方向都向左每个数的方向都向左.1,2,k的邻位互换程序的邻位互换程序LH(k):若若 k的方向侧邻居的方向侧邻居ak,则则 a k 互换互换,返回返回;否则否则 执行执行LH(k-1),k的方向反向的方向反向,返回返回.定义定义:若数若数k方向侧邻居方向侧邻居ak的数的方向的数的方向.若还有活动数若还有活动数,转转2.注注:(1)编程时可进一步改进编程时可进一步改进.(2)可以直接计算每个排列的序号可以直接计算每个排列的序号.(p58)例例:计算计算25143的序号的序号.第4页，本讲稿共12页排列与逆序列排列与逆序列(p58-61)设设i1in是是1,n的一个全排列的一个全排列令令aj是是j的左边大于的左边大于j的数的个数的数的个数,则称则称a1an是是i1in的逆序列的逆序列.注注:an=0.例例:31524的逆序列是的逆序列是12010还原逆序列还原逆序列:1.从大到小还原从大到小还原,2.从小到大还原从小到大还原 逆序列的生成逆序列的生成,计算逆序数的算法计算逆序数的算法第5页，本讲稿共12页生成全体组合生成全体组合(p62-64)S=xn-1,x1,x0,A S,A an-1a1a0,若若 xi A,则则 ai=1,否否则则 ai=0.称称为为n元元组组的字典序的字典序.缺点缺点:每次每次变变多个元素多个元素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 第6页，本讲稿共12页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.第7页，本讲稿共12页生成生成n阶反射阶反射Gray码的算法码的算法(p68-69)(1)从从an-1a1a0=000开始开始(2)当当an-1a1a0 100时时,i)计计算算 =an-1+a0(1的个数的个数),ii)若若 偶偶,则则 a0 a0,iii)若若 奇奇,则则找找 j 0 使得使得ajaj-1a0=100,执执行行 aj+1 aj+1.例例:10111100,0001111 的后的后继继,前前驱驱.定理定理:上述算法上述算法产产生生n阶阶Gray码码.证证明明:数学数学归纳归纳法法.第8页，本讲稿共12页生成生成S=1,2,n的的r组合组合(p69-72)i1,ir S表示为表示为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的序号是的序号是第9页，本讲稿共12页本章小结与作业本章小结与作业排列的邻位互换生成法排列的邻位互换生成法排列的逆序列排列的逆序列排列和组合的字典序法排列和组合的字典序法组合的组合的Gray反射码反射码r-组合的字典序法组合的字典序法作业作业:第四章第四章 ex7,ex15,ex24,ex33,ex52.思考题思考题:ex25.第10页，本讲稿共12页二项式定理二项式定理(p81,p84)Pascal公式公式 二项式定理二项式定理(the binomial theorem)第11页，本讲稿共12页一些恒等式一些恒等式(p87,p89)第12页，本讲稿共12页