组合数学：1-2-排列组合的生成

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!

2、=(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的算法如下：,.,反过来, 由(a3,a2,a1)= (301)也可以得到排列4213，,下面我们试图将n-1个元素的序列(an-1,a1)与n个元素的排列建立起一一对应关系。,例如：p=4213 (a3,a2,a1)= (

3、301),序列(an-1,a1)与某一排列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) )。 缺点是这种对应关系需要通过序列转换，即两层对应关系，多一层计算量。,一个全排列可看做一个字符串，字符串可有前缀、后缀。关键是如何生成给定全排列的下一个排列。

4、,(C) 字典序法,字典序：对于两个序列a1ak和b1bk ，若存在t，使得ai=bi, it，但atbt ，则称,例如对于字符集1,2,3，较小的数字较先，这样按字典序生成的全排列是：123,132,213,231,312,321,所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。,839647521的下一个为839651247。,例如：839647521是1-9的一个排列，求出下一个。,(1-9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没

5、有下一个了。),(1) 从右向左扫描找出第一次出现下降的位置。(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 p

6、2npn-1,np1 p2pn-1,p1 p2pn-1n,基于直接生成法，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

7、 1 3 2 1 3 2 1 3 2 3 1 2 3 1 2 3 1 2 3 1 2,对给定的一个整数k，我们赋其一个方向，即在其上写一个箭头（指向左侧或右侧）,下面我们用较正式的语言来说这件事。,对上述过程，一般地，对于i，将前一步所得的每一排列重复 i 次，然后将 i 由第一排的最后往前移，至最前列，正好走了 i 次,下一个接着将 i 放在下一排列的最前面，然后依次往后移，一直下去即得 i 元排列。,显然1永远不可移；,(1) n是第一个数，且其方向指向左侧，,(2) n是最后一个数，且其方向指向右侧。,考虑1,2n的一个排列，其上每一个整数都给了一个方向。,我们称整数k是可移的(Mobi

8、le&Active)，如果它的箭头所指的方向的邻点小于它本身。,例如 中6、3、5都是可移的。,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；,这等