Chap1-2排列组合生成、可重组合.ppt

1.6全排列的生成算法,全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。,这里介绍4种全排列算法：,(A) 直接生成法 (B) 序数法 (C) 字典序法 (D) 换位法,1.6.1 直接生成法,递推算法：假设已经生成n-1个数的所有(n-1)!个全排列，将n插入到每一个排列的前面、第12之间、第23之间、。最后，即得到n个数的所有n(n-1)!=n! 个全排列。,优点是生成简便，缺点是速度慢。,1.6.2 序数法,n的十进制表示:,n的p进制表示,1. 6.2 序数法,我们来看另一种表示,n!=(n-1)+1)(n-1)!=(n-1)(n-1)!+(n-1)!,同理，,(n-1)!=(n-2)(n-2)!+(n-2)!,故,n!= (n-1)(n-1)!+ (n-2)(n-2)!+22!+2!,不难证明，从0到n!-1的任何数m可唯一的表示为,其中,所以从0到n!-1的n!个整数与,(an-1,an-2,a2,a1),一一对应。,另一方面，不难从m算出an-1,an-2,a2,a1.,1. 6.2 序数法,算法如下：,.,1. 6.2 序数法,1. 6.2 序数法,反过来, 由(a3,a2,a1)= (301)也可以得到排列4213，,下面我们试图将n-1个元素的序列(an-1,a1)与n个元素的排列建立起一一对应关系.,其中,例 p=4213 (a3,a2,a1)= (301),_ _ _ _,4,3,2,1,而a2=0,说明3的右边没有比它更小的，故3放在最右端，,考虑a1=1,容易得出，2右边还有一个空格放1，于是得到了排列4213。,由a3=3, 知4放在空格的最左端,1. 6.2 序数法,方法如下,1. 6.2 序数法,这个算法的优点是建立了自然序数和排列之间的一一对应关系（通过n-1个元素的序列(an-1,a1) ）。 缺点是这种对应关系需要通过序列转换， 即两层对应关系，多一层计算量。,1.6.3字典序法,字典序：对于两个序列a1ak和b1bk ，若存在t，使得ai=bi, it，但atbt ，则称,例字符集1,2,3,较小的数字较先,这样按字典序生成的全排列是: 123,132,213,231,312,321。, 一个全排列可看做一个字符串，字符串可有 前缀、后缀。,1.6.3字典序法,1）生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。,例 839647521是1-9的排列。19的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则从右向左扫描找出第一次出现下降的位置。,1.6.3字典序法,求839647521的下一个排列,7 5 2 1,7,47,45,5,42,2,41,1,在后缀7521中找出比4大的数,7 5,找出其中比4大的最小数,5,5,4 、5 对换,8396 7 21,5,4,后缀变为7421,将此后缀翻转,12 4 7,接上前缀83965得到839651247 即839647521的下一个。,例,为后缀,大于4的用橙色表示 小于4的用绿色表示,找出比右边数字小的第一个数4,1.6.3字典序法,一般而言，设P是1,n的一个全排列。,P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1Pn,P= P1P2Pj-1PkPnPk+1PjPk-1Pj+1即是P的下一个,对换Pj，Pk，将Pj+1Pk-1PjPk+1Pn翻转，,j=maxi|PiPj,该算法的优点是排列清晰，而且保持着字典序。缺点是算法较繁琐。,1.6.4换位法,给定n-1的一个排列,将n 由最右端依次插入排 列 ，即得到n个n的排列：,p1 p2npn-1,np1 p2pn-1,p1 p2pn-1n,基于直接生成法 n的全排列可由n-1的全排列生成：,(1) 1,(2) 1 1,例, n=4,(3),3,3,3,3,3,3,2,2,1 2 3 1 2 3 1 2 3 1 2 3 1 3 2 1 3 2 1 3 2 1 3 2 3 1 2 3 1 2 3 1 2 3 1 2,3 2 1 3 2 1 3 2 1 3 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 3 2 1 3 2 1 3 2 1 3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,对上述过程，一般地，对i，将前一步所得的每一排列重复i次，然后将i由第一排的最后往前移，至最前列，正好走了i次,下一个接着将i放在下一排列的最前面，然后依次往后移，一直下去即得i元排列。,对给定的一个整数k，我们赋其一个方向，即在其上写一个箭头（指向左侧或右侧）,下面我们用较正式的语言来说这件事。,1.6.4换位法,考虑1,2n的一个排列，其上每一个整数都给了一个方向，我们称整数k是可移的(Mobile&Active),如果它的箭头所指的方向的邻点小于它本身。例如,中6、3、5都是可移的。显然1永远不可移，n除了以下两种情形外，它都是可移的:,(1) n是第一个数，且其方向指向左侧,(2) n是最后一个数，且其方向指向右侧.,1.6.4换位法,2，当存在可移数时 找最大的可移数m 将m与其箭头所指的邻数互换位置 将所得排列中比m大的数p的方向调整，即改为相反方向。,于是，我们可由 按如下算法产生所有排列,算法,1，开始时：,1.6.4换位法,1 2 3 1 2 3 1 2 3 1 2 3 1 3 2 1 3 2 1 3 2 1 3 2 3 1 2 3 1 2 3 1 2 3 1 2,3 2 1 3 2 1 3 2 1 3 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 3 2 1 3 2 1 3 2 1 3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,1.7 组合的生成,设从1,n中取r元的一个组合为C1C2Cr,不妨设C1C2Cr ,则 iCi(n-r+i), i=1,2,r,（1）找j=maxi|Cin-r+i,这等于给所有的组合建立了字典序。,生成C1C2Cr的下一个组合的算法如下,（2）令Cj=Cj+1,（3）令Ci=Ci-1+1,i=j+1,r,n中取r的排列生成可以由组合生成和全排列生成结合而得到。,1.8多重集的排列和组合,多重集元素可以多次出现的集合，即元素可以重复。我们把某个元素ai出现的次数ni(ni=0,1,2,)叫做该元素的重复数，通常把含有k种不同元素的多重集S记作,1.8.1可重排列,例1 求不多于4位数的二进制数的个数.,解：所求的标志数是多重集2红旗，3黄旗的排列 数，故N=5!/(2!3!)=10,例2 用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志?,1.8.1可重排列,总结,4)若r n ,且存在i, , 则对N没有一般的求解公式，具体解法以后再说。,设,则S的r-排列数N满足：,1)若r n,则N = 0;,2)若r = n, 则 N=,3)若r n ,且对所有的i, , 则,1.8.2可重组合,这个计数问题相当于r个相同的球放入k个不同的盒子里，个数没有限制的计数.,1.8.2 可重组合,r个相同的球 / 001001100 / / k-1个相同的盒壁,而后一问题又可转换为r个相同的球与k-1个相同 的盒壁的排列的问题。,则所求计数为C(k+r-1,r).,1.8.2可重组合,另证,不妨假设k个不同元素为1,2,k，设某一个r可重组合为b1,b2,br。由于允许重复，可以假设,这相当于从1到k+r-1中取r个不允许重复的组合。很容易验证，这是一个一一对应，从而定理成立。,第二个证明可说一种“拉伸压缩”技巧。不可谓 不巧妙。但仍不如第一证明来的明快，由此可见 组合证明的功效。,任取一个所求的r组合，从中拿走每个元素一个就得到S的一个r-k组合，反之,对于S的一个r-k组合，加入元素a1,a2,ak 就得到所求组合，所以其组合数即为S的r-k可重组合数。,1. 8.2可重组合,总结,设 则S的r-组合数N满足： 1)若r n, 则 N=0; 2)若r = n, 则 N=1; 3)若r n ,且对所有的i, ,则N=C(k+r-1,r); 4)若r n ,且存在i, , 则对N没有一般的求解公式，具体解法以后再说。,1.8.2可重组合,取r个无区别的球放进k个有标志的盒子，每个盒 子中的球的数目不加限制, 允许重复的组合数即 其方案数。,典型模型,定理1.3 线性方程 的非负整数解的个数为C(k+r-1,r) 。,1.8.3不相邻的组合,不相邻的组合是指从n=1,2,n中取r 个，不允许重