1、1.5 全排列的生成算法全排列的生成算法1.2 一一对应原理Yiqiang Wei 1.5 全排列的生成算法全排列的生成算法 就是对于给定的字符集 ，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 这里介绍全排列算法四种：(A)字典序法(B)逆序数法(C)递减 进位制数法(D)邻位对换法Yiqiang Wei 1.5 全排列的生成算法1.5.1字典序法字典序： 设字符集 A=a1,a2, ， an有序： a1 a2 an则字符串集 = p1p2 pm| pi A， m N 按下列方式定义的序称为 字典序 ：p1p2 pm q1q2 ql 当且仅当p1=q1， p2=q2， ， pm =
2、qm 或存在 k m-1,使得 p1=q1， ， pk=qk， pk+1 qk+1 Yiqiang Wei 1.5 全排列的生成算法 按字典序规定两个全排列的先后是从左到右逐个比较对应的字符的先后。字典序法： 一个全排列可看做一个字符串，按字典序给出全排列的序称为字典序法例如 ，字符集 1,2,3,较小的数字较先 ,这样按字典序生成的全排列顺序是 :123,132,213,231,312,321。 两个字符串， 相同前缀越长的越靠近 。Yiqiang Wei 1.5 全排列的生成算法如何 生成给定全排列的下一个排列所谓 一个的下一个 就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽
3、可能 长的 共同前缀 ，也即变化限制在尽可能 短 的 后缀上。例如 839647521是 1-9的排列。 19 的排列最前面的是 123456789，最后面的是 987654321，从右向左扫描若都是增的，就到 了 987654321，也就没有下一个了。否则找出第一次出现下降的位置。Yiqiang Wei 在 839647521中从右向左第一个小于右边数字的是元素 47 5 2 1 74 7 422411在后缀 7521中找出比 4大的数 7 5找出其中比 4大的最小数 55 4 、 5 对换 8396 7 214后缀变为 7421 将此后缀翻转 12 4 7接上前缀 83965得到 8396
4、51247即 839647521的下一个排列为 839651247 。为后缀大于 4的用 橙 色表示小于 4的用 绿 色表示1.5 全排列的生成算法Yiqiang Wei 1.5 全排列的生成算法首先，在排列中从右向左找出第一个小于右边元素的元素，记为 a 。右边部分构成 后缀 。由字典序法产生下一个排列的步骤其次，在后缀找出大于 a 的最小元素，记为 b第三，对换元素 a 与 b最后，对新的后缀进行翻转，得到所求。Yiqiang Wei 1.5 全排列的生成算法由字典序法产生下一个排列的步骤例 1 在字典序下求 731598642的下一个 排列Yiqiang Wei 在 1,n的全排列中 ,n n-1 321是最后一个排列 ,其中介数是 (n-1,n-2,.,3,2,1)其序号为n-1kk!k=1另一方面可直接看出其序号为 n!-1n-1 n-1于是 n!-1= kk! 即 n!=kk! +1k=1 k=1Yiqiang Wei 1.5.1字典序法一般而言，设 P是 1,n的一个全排列。P=P1P2 Pn=P1P2P j-1PjPj+1P k-1PkPk+1 Pnj=maxi|PiPj对换 Pj， Pk，将 Pj+1P k-1PjPk+1 Pn翻转，P= P1P2P j-1PkPnP k+1PjPk-1P j+1即 P的下一个
