排列组合的生成.ppt
排列组合的生成 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望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)!=(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 p=4213(a3,a2,a1)=(301)序列序列(an-1,a1)与某一排列与某一排列p p=p1p2pn之间的对应之间的对应关系为：关系为：ai 表示排列表示排列p p中的数中的数i+1所在位置的右边比它小的数所在位置的右边比它小的数的个数。的个数。_ _ _ _432 1而而a2=0,说明说明3的右边没有比它更小的，故的右边没有比它更小的，故3放在最放在最右端，右端，考虑考虑a1=1,容易得出，容易得出，2右边还有一个空格放右边还有一个空格放1，于是，于是得到了排列得到了排列4213。由由a3=3,知知4放在空格的最左端放在空格的最左端,这个算法的这个算法的优点优点是建立了自然序数和排列之间的是建立了自然序数和排列之间的一一一对应一对应关系关系(通过通过n-1个元素的序列个元素的序列(an-1,a1)。缺点缺点是这种对应关系需要通过序列转换，即是这种对应关系需要通过序列转换，即两层对两层对应关系，多一层计算量应关系，多一层计算量。一个全排列可看做一个字符串，字符串可有一个全排列可看做一个字符串，字符串可有前缀、前缀、后缀后缀。关键是如何生成给定全排列的关键是如何生成给定全排列的下一个排列下一个排列。(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，也就没有下一个了。，也就没有下一个了。)(1)从右向左扫描找出第一次出现下降的位置。从右向左扫描找出第一次出现下降的位置。(4)(2)在在4的右边按从左往右的顺序找出最后一个比的右边按从左往右的顺序找出最后一个比4大的数字大的数字(5)，交换这两个数字，得到，交换这两个数字，得到839657421。(3)把把5后面的数字顺序完全颠倒过来即得到：后面的数字顺序完全颠倒过来即得到：P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1PnP1P2Pj-1PkPnPk+1PjPk-1Pj+1即是即是P的下一个。的下一个。(2)对换对换 Pj，Pk；(1)找出找出 j=max i|PiPj；该算法的该算法的优点优点是是排列清晰排列清晰，而且，而且保持着字典序保持着字典序。缺点缺点是算法是算法较繁琐较繁琐。一般而言，设一般而言，设P是是1,n的一个全排列。的一个全排列。(3)将将 Pj+1Pk-1PjPk+1Pn翻转，翻转，p1 p2npn-1np1 p2pn-1p1 p2pn-1n基于直接生成法，基于直接生成法，n的全排列可由的全排列可由n-1的全排的全排列生成：列生成：(D)换位法换位法给定给定n-1的一个排列的一个排列,将将n 由最右端依次插入排由最右端依次插入排列列，即得到，即得到n个个n的排列：的排列：例如对于例如对于 n=4第三步：第三步：1 21 22 12 11 22 133333322第二步：第二步：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 3444444444444444444444444第四步：第四步：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对给定的一个整数对给定的一个整数k，我们赋其一个方向，即在其我们赋其一个方向，即在其上写一个箭头（指向左侧或右侧）上写一个箭头（指向左侧或右侧）下面我们用较正式的语言来说这件事。下面我们用较正式的语言来说这件事。kk或者或者对上述过程，一般地，对于对上述过程，一般地，对于i，将前一步所得的每，将前一步所得的每一排列重复一排列重复 i 次，然后将次，然后将 i 由第一排的最后往前移，由第一排的最后往前移，至最前列，正好走了至最前列，正好走了 i 次次,下一个接着将下一个接着将 i 放在下一放在下一排列的最前面，然后依次往后移，一直下去即得排列的最前面，然后依次往后移，一直下去即得 i 元排列。元排列。显然显然1永远不可移；永远不可移；(1)n是第一个数，且其方向指向左侧，是第一个数，且其方向指向左侧，(2)n是最后一个数，且其方向指向右侧。是最后一个数，且其方向指向右侧。考虑考虑1,2n的一个排列，其上每一个整数都给了一的一个排列，其上每一个整数都给了一个方向。个方向。我们称整数我们称整数k是是可移的可移的(Mobile&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 3444444444444444444444444设从设从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的排列生成可以由组合生成和全排列生成的排列生成可以由组合生成和全排列生成结合而得到。结合而得到。
