《排列组合的生成.ppt》由会员分享，可在线阅读，更多相关《排列组合的生成.ppt（19页珍藏版）》请在三一办公上搜索。
1、1.2 排列组合生成算法,全排列的生成算法 组合的生成算法 一般排列的生成算法,1.全排列的生成算法,全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。,这里介绍4种全排列算法：,(A)直接生成法(B)序数法(C)字典序法(D)换位法,递推算法：假设已经生成n-1个数的所有(n-1)!个全排列，将n插入到每一个排列的前面、第12之间、第23之间、。最后，即得到n个数的所有n(n-1)!=n!个全排列。,优点是生成简便，缺点是速度慢。,(A)直接生成法,n的p进制表示：,(B)序数法,n的十进制表示：,我们来看另一种表示,n!=(n-1)+1)(n-1)
2、!=(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的算法如下：,.,反过来,由(a3,a2,a1)=(301)也可以得到排列4213，,下面我们试图将n-1个元素的序列(an-1,a1)与n个元素的排列建立起一一对应关系。,例如：p=4213(a3,a2,a1)=(301),序列(an-1,a1)与某一排
3、列p=p1p2pn之间的对应关系为：ai 表示排列p中的数i+1所在位置的右边比它小的数的个数。,_ _ _ _,4,3,2,1,而a2=0,说明3的右边没有比它更小的，故3放在最右端，,考虑a1=1,容易得出，2右边还有一个空格放1，于是得到了排列4213。,由a3=3,知4放在空格的最左端,这个算法的优点是建立了自然序数和排列之间的一一对应关系(通过n-1个元素的序列(an-1,a1)。缺点是这种对应关系需要通过序列转换，即两层对应关系，多一层计算量。,一个全排列可看做一个字符串，字符串可有前缀、后缀。关键是如何生成给定全排列的下一个排列。,(C)字典序法,字典序：对于两个序列a1ak和b
4、1bk，若存在t，使得ai=bi,it，但atbt，则称,例如对于字符集1,2,3，较小的数字较先，这样按字典序生成的全排列是：123,132,213,231,312,321,所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。,839647521的下一个为839651247。,例如：839647521是1-9的一个排列，求出下一个。,(1-9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。),(1)从右向左扫描找出第一次出现下降的位置
5、。(4),(2)在4的右边按从左往右的顺序找出最后一个比4大的数字(5)，交换这两个数字，得到839657421。,(3)把5后面的数字顺序完全颠倒过来即得到：,P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1Pn,P1P2Pj-1PkPnPk+1PjPk-1Pj+1即是P的下一个。,(2)对换 Pj，Pk；,(1)找出 j=max i|PiPj；,该算法的优点是排列清晰，而且保持着字典序。缺点是算法较繁琐。,一般而言，设P是1,n的一个全排列。,(3)将 Pj+1Pk-1PjPk+1Pn翻转，,p1 p2npn-1,np1 p2pn-1,p1 p2pn-1n,基于直接生成法
6、，n的全排列可由n-1的全排列生成：,(D)换位法,给定n-1的一个排列,将n 由最右端依次插入排列，即得到n个n的排列：,例如对于 n=4,第三步：,3,3,3,3,3,3,2,2,第二步：1 1,第一步：1,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 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
7、2,对给定的一个整数k，我们赋其一个方向，即在其上写一个箭头（指向左侧或右侧）,下面我们用较正式的语言来说这件事。,对上述过程，一般地，对于i，将前一步所得的每一排列重复 i 次，然后将 i 由第一排的最后往前移，至最前列，正好走了 i 次,下一个接着将 i 放在下一排列的最前面，然后依次往后移，一直下去即得 i 元排列。,显然1永远不可移；,(1)n是第一个数，且其方向指向左侧，,(2)n是最后一个数，且其方向指向右侧。,考虑1,2n的一个排列，其上每一个整数都给了一个方向。,我们称整数k是可移的(Mobile&Active)，如果它的箭头所指的方向的邻点小于它本身。,例如 中6、3、5都是
8、可移的。,n除了以下两种情形外，它都是可移的：,于是，我们可由 按如下算法产生所有排列：,1、开始时：,2、当存在可移数时，,(a)找最大的可移数m；,(b)将m与其箭头所指的邻数互换位置；,(c)将所得排列中比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,n中取r元的一个组合为C1C2Cr，,不妨设C1Cr,则 iCi(n-r+i),i=1,2,r。,(1)找 j=max i|Cin-r+i；,这等于给所有的组合建立了字典序。,生成C1C2Cr的下一个组合的算法如下：,(2)令 Cj=Cj+1；,(3)令 Ci=Ci-1+1,i=j+1,r。,2.组合的生成算法,3.一般排列的生成算法,n中取r的排列生成可以由组合生成和全排列生成结合而得到。,
