chap1-2排列组合生成、可重组合

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

1、1.6全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。这里介绍4种全排列算法：(A)直接生成法(B)序数法(C)字典序法(D)换位法1.6.1直接生成法递推算法：假设已经生成n-1个数的所有(n-1)!个全排列，将n插入到每一个排列的前面、第12之间、第23之间、。。。最后，即得到n个数的所有n(n-1)!=n!个全排列。优点是生成简便，缺点是速度慢。1.6.2序数法n的十进制表示:n的p进制表示1.6.2序数法我们来看另一种表示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)!+…+2×2!+2!不难证明，从0到n!-1的任何数m可唯一的表示为其中所以从0到n!-1的n!个整数与(an-1,an-2,…a2,a1)一一对应。另一方面，不难从m算出an-1,an-2,…a2,a1.1.6.2序数法算法如下：…………….1.6.2序数法1.6.2序数法反过来,由(a3,a2,a1)=(301)也可以得到排列4213，下面我们试图将n-1个元素的序列(an-

3、1,…,a1)与n个元素的排列建立起一一对应关系.其中例p=4213(a3,a2,a1)=(301)____4321而a2=0,说明3的右边没有比它更小的，故3放在最右端，考虑a1=1,容易得出，2右边还有一个空格放1，于是得到了排列4213。由a3=3,知4放在空格的最左端,1.6.2序数法方法如下1.6.2序数法这个算法的优点是建立了自然序数和排列之间的一一对应关系（通过n-1个元素的序列(an-1,…,a1)）。缺点是这种对应关系需要通过序列转换，即两层对应关系，多一层计算量。1.6.3字典序法字典序：对于两个序列a1…

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

5、右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则从右向左扫描找出第一次出现下降的位置。1.6.3字典序法求839647521的下一个排列752174＜74<554>224>11在后缀7521中找出比4大的数75找出其中比4大的最小数554、5对换839672154后缀变为7421将此后缀翻转1247接上前缀83965得到839651247即839647521的下一个。[例]为后缀大于4的用橙色表示小于4的用绿色表示找出比右边数字小的第一个数41.6.3字典序法一般而言，设P是[1,n]的一个全排列。P=P1

6、P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…PnP’=P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即是P的下一个对换Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻转，j=max{i

7、Pi

8、Pi>Pj}该算法的优点是排列清晰，而且保持着字典序。缺点是算法较繁琐。1.6.4换位法给定[n-1]的一个排列п,将n由最右端依次插入排列п，即得到n个[n]的排列：p1p2…npn-1np1p2…pn-1…p1p2…pn-1n基于直接生成法[n]的全排列可由[n-1]的全

9、排列生成：(1)1(2)11例,n=4(3)12122121122133333322123123123123132132132132312312312312321321321321231231231231213213213213444444444444444444444444对上述过程，一般地，对i，将前一步所得的每一排列重复i次，然后将i由第一排的最后往前移，至最前列，正好走了i次,下一个接着将i放在下一排列的最前面，然后依次往后移，一直下去即得i元排列。对给定的一个整数k，我们赋其一个方向，即在其上写一个箭头（指向左侧或右侧

10、）下面我们用较正式的语言来说这件事。kk或者1.6.4换位法考虑{1,2…n}的一个排列，其上每一个整数都给了一个方向，我们称整数k是可移的(Mobile&Active),如果它的箭头所指的方向的邻点小于它本身。例如中6、3、5都是可移的。显然1永远不可移，n除