排列组合生成算法.ppt

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

1、1.6全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。1.6全排列的生成算法这里介绍3种全排列算法：(A)序数法(B)字典序法(C)换位法1.6.1序数法n的十进制表示：n的p进制表示我们来看另一种表示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可唯一的

2、表示为m=an-1(n-1)!+an-2(n-2)!+…+a11!,其中0

3、)与n个元素的排列建立起一一对应关系设序列(an-1,…,a1)对应某一排列p=p1p2…pn,其中ai：排列p中数i+1所在位置的右边比i+1小的数的个数,i=1,2,…,n-1例p=4213--(a3,a2,a1)=(301)反过来，由(a3,a2,a1)=(301)也可以得到排列4213，方法如下由a3=3,4放在空格的最左端,____4321而a2=0,说明3的右边没有比它更小的，故3放在最右端，考虑a1=1,容易得出，2右边还有一个空格，放1，于是得到了排列4213。实际上，我们可以从1开始构造排列

4、1，写下12，考虑a1,它只可取0或1，若取0，则2必在1的后边，否则，它在1的前边。3，考虑a2,它可取0,1,2.若取0，3必放在上一步得到的两个数的排列的后边，若a2=1,则3必放在第二步得到的两数的排列的中间，若a2=2,则3必放在第二步得到的排列的两数的前边，…1k+1，考虑ak,0≤ak≤k,(1),ak=0,k+1必放在第k步得到的排列的这k个数的最后面；(2),ak=1,k+1必放在第k步得到的排列的这k个数的倒数两个数中间，….(j),ak=j,k+1必放在第k步得到的排列的这k个数的倒数j,

5、j+1这两个数之间；….1.6.2字典序法对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。1.6.2字典序法[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。※※一个全排列可看做一个字符串，字符串可有前缀、后缀。1.6.2字典序法1）生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

6、1.6.2字典序法[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。1.6.2字典序法求839647521的下一个排列752174＜74<554>224>11在后缀7521中找出比4大的数75找出其中比4大的最小数554、5对换839672154后缀变为7421将此后缀翻转1247接上前缀83965得到839651247即839647521的下一个。[

7、例]为后缀大于4的用橙色表示小于4的用绿色表示找出比右边数字小的第一个数41.6.2字典序法一般而言，设P是[1,n]的一个全排列。P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pnj=max{i

8、Pi

9、Pi>Pj}对换Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻转，P’=P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个1.6.3换位法思想[n]的全排列可由[n-1]的全排列生成：给定[n-1]的一个排列п,将n由最右端依次插

10、入排列п，即得到n个[n]的排列：p1p2…npn-1np1p2…pn-1…p1p2…pn-1n(1)111例,n=4(3)12122121122133333322123123123123132132132132312312312312321321321321231231231231213213213213444444444444444444444444对上述过程，一般地，对i，将前一