排列组合生成算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.6,全排列的生成算法,全排列的生成算法,就是对于给定的字符集，用有效的方法将所有可能的全排列,无重复无遗漏,地枚举出来。,1.6,全排列的生成算法,这里介绍,3,种全排列算法,：,(,A),序数法,(,B),字典序法,(,C),换位法,1.6.1,序数法,n,的,十进制表示,：,n,的,p,进制表示,我们来看另一种表示,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)!+2*2!+2!,不难证明,，,从,0,到,n!-1,的任何数,m,可唯一的表示为,m=,a,n-1,(,n-,1,)!+,a,n-2,(,n-,2,)!+,a,1,1,!,其中,0,a,i,i.,所以从,0,到,n!,-1,的,n!,个整数与,(,a,n-,1,a,n-2,a,2,a,1,),一一对应。另一方面，不难从,m,算出,a,n-,1,a,n-2,a,2,a,1,.,=,=,算法如下,：,m,=,m,1,0,m n!-1,m,1,=2m,2,+,k,1,0 k,1,1,m,2,=3m,3,+k,2,0 k,2,2,.,m,n-2,=(n-1)m,n-1,+,k,n-2,0 k,n-2,n-2,m,n-1,=,k,n-1,0 k,n-1,n-1,(,k,n-1,k,2,k,1,),m,下面我们试图将,n-1,个元素的序列,(a,n-1,a,1,),与,n,个元素的排列建立起一一对应关系,设,序列,(,a,n-,1,a,1,),对应某一排列,p=,p,1,p,2,p,n,其中,a,i,：排列,p,中数,i+1,所在位置的右边比,i+1,小的数的个数,i=1,2,n-1,例,p=4213-,(,a,3,a,2,a,1,)=(301),反过来，由,(,a,3,a,2,a,1,)=(301),也可以得到排列,4213,，方法如下,由,a,3,=3,4,放在空格的最左端,_ _ _ _,4,3,2,1,而,a,2,=0,说明,3,的右边没有比它更小的，故,3,放在最右端，,考虑,a,1,=1,容易得出,，,2,右边还有一个空格,，放,1,，于是得到了排列,4213,。,实际上，我们可以从,1,开始构造排列,1,，,写下,1,2,，考虑,a,1,它只可取,0,或,1,，若取,0,，则,2,必在,1,的后边，否则，它在,1,的前边。,3,，考虑,a,2,它可取,0,1,2.,若取,0,，,3,必放在上一步得到的两个数的排列的后边，若,a,2,=1,则,3,必放在第二步得到的两数的排列的中间，若,a,2,=2,则,3,必放在第二步得到的排列的两数的前边，,1,k+1,，考虑,a,k,0,a,k,k,(1),a,k,=0,k,+1,必放在第,k,步得到的排列的这,k,个数的最后面；,(2),a,k,=1,k+1,必放在第,k,步得到的排列的这,k,个数的倒数两个数中间，,.,(j),a,k,=j,k+1,必放在第,k,步得到的排列的这,k,个数的倒数,j,j,+1,这两个数之间；,.,1.6.2,字典序法,对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。,1.6.2,字典序法,例,字符集,1,2,3,较小的数字较先,这样按字典序生成的全排列是,:,123,132,213,231,312,321,。,一个全排列可看做一个字符串，字,符串可有,前缀,、,后缀,。,1.6.2,字典序法,1,）,生成给定全排列的下一个排列,所谓,一个的下一个,就是,这一个,与,下一个,之间,没有其他的,。这就要求这一个与下一个有尽可能,长,的,共同前缀,，也即变化限制在尽可能,短,的,后缀,上。,1.6.2,字典序法,例,839647521,是,1-9,的排列。19的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到,了,987654321，也就没有下,一个了。否则找出第一次出现下降的位置,。,1.6.2,字典序法,求,8396,4,7521,的下一个排列,7 5 2 1,7,4,7,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.2,字典序法,一般而言，设,P,是,1,n,的一个全排列。,P=P,1,P,2,P,n,=P,1,P,2,P,j-1,P,j,P,j+1,P,k-1,P,k,P,k+1,P,n,j=maxi|P,i,P,j,对换,P,j,，,P,k,，将,P,j+1,P,k-1,P,j,P,k+1,P,n,翻转，,P,=P,1,P,2,P,j-1,P,k,P,n,P,k+1,P,j,P,k-1,P,j+1,即,P,的下一个,1.6.3,换位法,思想,n,的全排列可由,n-1,的全排列生成：,给定,n-1,的一个排列,将,n,由最右端依次插入排列,，,即得到,n,个,n,的排列：,p,1,p,2,n,p,n-1,n,p,1,p,2,p,n-1,p,1,p,2,p,n-1,n,(1)1,1,1,例,n=4,(3),1 2,1 2,2 1,2 1,1 2,2 1,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,，,我们赋其一个方向，即在其上写一个箭头（指向左侧或右侧）,或者,k,k,考虑,1,2n,的一个排列，其上每一个整数都给了一个方向，我们称整数,k,是可移的,(Mobile&Active),如果它的箭头所指的方向的邻点小于它本身。例如,中,6,、,3,、,5,都是可移的。显然,1,永远不可移，,n,除了以下两种情形外，它都是可移的,:(1),n,是第一个数，且其方向指向左侧,(2),n,是最后一个数，且其方向指向右侧,于是，我们可由,按如下算法产生所有排列,算法,1,，,开始时：,2,，当存在可移数时,找最大的可移数,m,将,m,与其箭头所指的邻数互换位置,将所得排列中比,m,大的数,p,的方向调整，即改为相反方向。,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,元的组合全体为,C(n,r).,C,1,C,2,C,r,C(n,r).,不妨设,C,1,C,2,C,r,i,C,i,(,n,r+i),i=1,2,r,令,j=maxi|C,i,n,r+i.,则,C,1,C,2,C,r,的下一个组合为,C,1,C,2,C,j-1,(C,j,+1)(C,j,+2)(C,j,+,r,j+1),这等于给,C(n,r),的元素建立了,字典序,。,12,r,的序号为,0,，,n-r+1 n-r+2n,的序号为,C(n,r,)1,1.7,组合的生成,例,在,C(10,4),中,4679,的序号是首位小于,4,的组合的个数；首位是,4,，第,2,位小于,6,的组合的个数；前,2,位是,46,，第,3,位小于,7,的组合的个数；前,3,位是,467,，第,4,位小于,9,的组合的个数之和。,反之，也可以由序号求组合,。,1.8,多重集的排列和组合,多重集,元,素可以多次出现的集合，即元素可以重复。我们把某个元素,a,i,出现的次数,n,i,(,n,i,=0,1,2,),叫做该元素的重复数，通常把含有,k,种不同元素的多重集,S,记作,1.8.1,可重排列,定义 从一个多重,集,中有序选取的,r,个元素叫做,S,的一个,r,-(,可重,),排列。当,时也叫做,S,的一个排列,.,定理,设多重集,则的,r-(,可重,),排列数是,r,k,推论,例,求不多于,4,位数的二进制数的个数,解：所求的标志数是多重集,2,红旗，,3,黄旗,的排列,数，故,N=5!/(2!*3!)=10,例,用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？,总结,设,则,S,的,r-,排列数,N,满足：,1),若,r,n,则,N,=0;,2),若,r=n,则,N=,3),若,r,n,且对所有的,i,则,4,若,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,个无区别的球放进,n,个有标志的盒子，每个盒子中的球的数目不加限制，允许重复的组合数即其方案数。,定理,1.3,r,个无区别的球放进,n,个有标志的盒子，每个盒子中的球的数目不限的方案数是,C(n+r-1,r),种。,1.8.3,不相邻的组合,不,相邻的组合是指从,n=1,2,n,中取,r,个，不允许重复且不存在,i,i,+1,两个相邻的数同时出现于一个组合中的组合,定理,1.4,从,n=1,2,n,中取,r,个作不相邻的组合，其个数为,C(n-r+1,r),1.8.3,不相邻的组合,证明,：用两种方法计算,n,的无重不相邻组合,C,(n,r),的计数问题,解法,1,00100100100100,其中不可含,11,/,/,共,n,位,r,个,1,/,/,以,1,结尾：,r-1,个,10,与,n-1-2(r-1),个,0,的排列,r-1+n-1-2(r-1)=n-r,这样的排列有,(n-r)!,=,(r-1)!(n-2r+1)!,(),n-r,r-1,1.8.3,不相邻的组合,以,0,结尾：,r,个,10,与,n-2r,个,0,的排列,r+n-2r=n-r,这样的排列有,(),个,(,)+(,)=(,),n-r,r,n-r n-r n-r+1,r-1 r r,1.8.3,不相邻的组合,解法,任给,a,1,a,2,a,r,C(n,r),a,1,a,2,a,r,令,f,：,a,1,a,2,a,r,b,1,b,2,b,r,b,i,=a,i,-i+1,i=1,2,r.,1,b,1,b,2,b,r,n-r+1,b,1,b,2,b,r,C(n-r+1,r),C(n,r)=C(n-r+1,r),