《排列组合的生成》PPT课件

《《排列组合的生成》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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)!=(n-1)

2、(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)一一对应。从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=p1p2…pn之间的对应关系为：ai表示排列p中的数i+1所在位置的右边比它小的数的个数。____4321而a2=0,说明3的右边没有比它更小的，故3放在最右端，考虑a1=1,容易得出，2右边还有一个空格放1，于是得到了排列4213。由a3=3,知4放在空格的最左端,这个算法的优点是建立了自然序数和排列之间的一一对应关系(通过n-1个元素的序列(an-1,…,a1))。缺点是这种对应关系需要通过序列转换，即两层对应关系，多一层计算量。一个全排列可看做一个字符串，字符串可有前缀、后缀。关键是如何生成给定全排列的下一个排列。(C)字典序法字典序：对于两个序列a1…ak和b

4、1…bk，若存在t，使得ai=bi,i

5、下降的位置。(4)(2)在4的右边按从左往右的顺序找出最后一个比4大的数字(5)，交换这两个数字，得到839657421。(3)把5后面的数字顺序完全颠倒过来即得到：P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…PnP1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即是P的下一个。(2)对换Pj，Pk；(1)找出j=max{i

6、Pi

7、Pi>Pj}；该算法的优点是排列清晰，而且保持着字典序。缺点是算法较繁琐。一般而言，设P是[1,n]的一个全排列。(3)将Pj+1…Pk-1PjPk+1…Pn翻转，p1p2…npn-1np

8、1p2…pn-1…p1p2…pn-1n基于直接生成法，[n]的全排列可由[n-1]的全排列生成：(D)换位法给定[n-1]的一个排列п,将n由最右端依次插入排列п，即得到n个[n]的排列：例如对于n=4第三步：12122121122133333322第二步：11第一步：1321321321321231231231231213213213213444444444444444444444444第四步：123123123123132132132132312312312312对给定的一个整数k，我们赋其一个方向，即在其上写一个箭头（指向左侧或右侧）下面我们用较正式的语言来说这件事。kk或者

9、对上述过程，一般地，对于i，将前一步所得的每一排列重复i次，然后将i由第一排的最后往前移，至最前列，正好走了i次,下一个接着将i放在下一排列的最前面，然后依次往后移，一直下去即得i元排列。显然1永远不可移；(1)n是第一个数，且其方向指向左侧，(2)n是最后一个数，且其方向指向右侧。考虑{1,2…n}的一个排列，其上每一个整数都给了一个方向。我们称整数k是可移的(Mobile&Active)，如果它的箭头所指的方向的邻点小于它本身。例如中6、3、5都是可移的。n除了以