排列组合的生成.ppt

1.2排列组合生成算法全排列的生成算法组合的生成算法一般排列的生成算法全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。这里介绍4种全排列算法：直接生成法序数法字典序法换位法递推算法：假设已经生成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)!+…+2×2!+2!其中不难证明，从0到n!-1的任何数m可唯一的表示为所以从0到n!-1的n!个整数与(an-1,an-2,…a2,a1)一一对应。12从m计算出an-1,an-2,…a2,a1的算法如下：…………….序列(an-1,…,a1)与某一排列p=p1p2…pn之间的对应关系为：ai表示排列p中的数i+1所在位置的右边比它小的数的个数。反过来,由(a3,a2,a1)=(301)也可以得到排列4213，下面我们试图将n-1个元素的序列(an-1,…,a1)与n个元素的排列建立起一一对应关系。例如：p=4213?(a3,a2,a1)=(301)01020304而a2=0,说明3的右边没有比它更小的，故3放在最右端，由a3=3,知4放在空格的最左端,考虑a1=1,容易得出，2右边还有一个空格放1，于是得到了排列4213。这个算法的优点是建立了自然序数和排列之间的一一对应关系(通过n-1个元素的序列(an-1,…,a1))。缺点是这种对应关系需要通过序列转换，即两层对应关系，多一层计算量。____一个全排列可看做一个字符串，字符串可有前缀、后缀。关键是如何生成给定全排列的下一个排列。A字典序：对于两个序列a1…ak和b1…bk，若存在t，使得ai=bi,it，但atbt，则称B例如对于字符集{1,2,3}，较小的数字较先，这样按字典序生成的全排列是：123,132,213,231,312,321C所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。D(C)字典序法839647521的下一个为839651247。例如：839647521是1-9的一个排列，求出下一个。(1-9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。)(1)从右向左扫描找出第一次出现下降的位置。(4)(2)在4的右边按从左往右的顺序找出最后一个比4大的数字(5)，交换这两个数字，得到839657421。(3)把5后面的数字顺序完全颠倒过来即得到：P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn找出j=max{i|PiPi+1}，k=max{i|PiPj}；一般而言，设P是[1,n]的一个全排列。P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即是P的下一个。对换Pj，Pk；该算法的优点是排列清晰，而且保持着字典序。缺点是算法较繁琐。将Pj+1…Pk-1PjPk+1…Pn翻转，p1p2…npn-1np1p2…pn-1…p1p2…pn-1n基于直接生成法，[n]的全排列可由[n-1]的全排列生成：(D)换位法给定[n-1]的一个排列п,将n由最右端依次插入排列п，即得到n个[n]的排列：例如对于n=4第三步：12122121123333322第二步：11第一步：13213213213212312312312312