组合数学之全排列的生成算法ppt课件.ppt

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

1、1.5全排列的生成算法1.2一一对应原理1.5全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。这里介绍全排列算法四种：(A)字典序法(B)逆序数法(C)递减进位制数法(D)邻位对换法1.5全排列的生成算法1.5.1字典序法字典序：设字符集A={a1,a2,…，an}有序：≤a1≤a2≤…≤an则字符串集Σ={p1p2…pm

2、pi∈A，m∈N}按下列方式定义的序称为字典序：p1p2…pm≤q1q2…ql当且仅当p1=q1，p2=q2，…，pm=qm或存在k≤m-1,使得p1=q1，…，pk=qk，pk+1≤qk+11

3、.5全排列的生成算法※※按字典序规定两个全排列的先后是从左到右逐个比较对应的字符的先后。字典序法：一个全排列可看做一个字符串，按字典序给出全排列的序称为字典序法例如，字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列顺序是:123,132,213,231,312,321。※※两个字符串，相同前缀越长的越靠近。1.5全排列的生成算法如何生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。例如839647521是1--9的排列。1—9的排列最前面的是123456789

4、，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。在839647521中从右向左第一个小于右边数字的是元素4752174＜74<554>224>11在后缀7521中找出比4大的数75找出其中比4大的最小数554、5对换839672154后缀变为7421将此后缀翻转1247接上前缀83965得到839651247即839647521的下一个排列为839651247。为后缀大于4的用橙色表示小于4的用绿色表示1.5全排列的生成算法1.5全排列的生成算法首先，在排列中从右向左找出第一个小于右边元素的元

5、素，记为a。右边部分构成后缀。由字典序法产生下一个排列的步骤其次，在后缀找出大于a的最小元素，记为b第三，对换元素a与b最后，对新的后缀进行翻转，得到所求。1.5全排列的生成算法由字典序法产生下一个排列的步骤例1在字典序下求731598642的下一个排列在[1,n]的全排列中,nn-1…321是最后一个排列,其中介数是(n-1,n-2,...,3,2,1)其序号为n-1∑k×k!k=1另一方面可直接看出其序号为n!-1n-1n-1于是n!-1=∑k×k!即n!=∑k×k!+1k=1k=11.5.1字典序法一般而言，设P是[1,n]的一个全排列。P=P1P2…Pn=P1P2…

6、Pj-1PjPj+1…Pk-1PkPk+1…Pnj=max{i

7、Pi

8、Pi>Pj}对换Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻转，P’=P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个1.5.1字典序法2)计算给定排列的序号839647521的序号即先于此排列的排列的个数。将先于此排列的排列按前缀分类。前缀先于8的排列的个数：7×8!第一位是8,先于83得的排列的个数：2×7!前2位是83,先于839得的排列的个数：6×6!先于此排列的的排列的个数：7×8!+2×7!+6×6!前3位是839,先于8396得的排列

9、的个数：4×5!+4×5!前4位是8396,先于83964得的排列的个数：2×4!+2×4!前5位是83964,先于839647得的排列的个数：3×3!+3×3!前6位是839647,先于8396475得的排列的个数：2×2!+2×2!前7位是8396475,先于83964752得的排列的个数：1×1!+1×1!297191前8位固定，则最后一位也随之固定将8!,7!,…,1!前面的系数抽出，放在一起得到72642321此数的特点：7：8的右边比8小的数的个数2：3的右边比3小的数的个数6：9的右边比9小的数的个数4：6的右边比6小的数的个数2：4的右边比4小的数的个数3：

10、7的右边比7小的数的个数2：5的右边比5小的数的个数1：2的右边比2小的数的个数72642321是计算排列839647521的序号的中间环节，我们称之为中介数。※这是一个很有用的概念。1.5.1字典序法一般而言,对于[1,9]的全排列中介数首位的取值为0—8，第2位的取值为0—7，以此类推，第8位的取值为0、1。从而序号可表示为：n-1∑ki(n-i)!i=1ki：Pi的右边比Pi小的数的个数i=1,2,…,n-11.5.1字典序法由中介数推出排列的算法[例]由72642321推算出839647521方法1：P1P