15组合数学之全排列的生成算法

1.5全排列的生成算法1.2一一对应原理[e-mail]1.5全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。这里介绍全排列算法四种：(A)字典序法(B)逆序数法(C)递减进位制数法(D)邻位对换法[e-mail]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=qm或存在k≤m-1,使得p1=q1，…，pk=qk，pk+1≤[e-mail]1.5全排列的生成算法※※按字典序规定两个全排列的先后是从左到右逐个比较对应的字符的先后。字典序法：一个全排列可看做一个字符串，按字典序给出全排列的序称为字典序法例如，字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列顺序是:123,132,213,231,312,321。※※两个字符串，相同前缀越长的越靠近。[e-mail]1.5全排列的生成算法如何生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。例如839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。[e-mail]在839647521中从右向左第一个小于右边数字的是元素4752174＜7455422411在后缀7521中找出比4大的数75找出其中比4大的最小数554、5对换839672154后缀变为7421将此后缀翻转1247接上前缀83965得到839651247即839647521的下一个排列为839651247。为后缀大于4的用橙色表示小于4的用绿色表示1.5全排列的生成算法[e-mail]1.5全排列的生成算法首先，在排列中从右向左找出第一个小于右边元素的元素，记为a。右边部分构成后缀。由字典序法产生下一个排列的步骤其次，在后缀找出大于a的最小元素，记为b第三，对换元素a与b最后，对新的后缀进行翻转，得到所求。[e-mail]1.5全排列的生成算法由字典序法产生下一个排列的步骤例1在字典序下求731598642的下一个排列[e-mail]在[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=[e-mail]1.5.1字典序法一般而言，设P是[1,n]的一个全排列。P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pnj=max{i|PiPi+1},k=max{i|PiPj}对换Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻转，P’=P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个[e-mail]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得的排列的个数：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：7的右边比7小的数的个数2：5的右边比5小的数的个数1：2的右边比2小的数的个数72642321是计算排列839647521的序号的中间环节，我们称之为中介数。※这是一个很有用的概念。[e-mail]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,…,[e-mail]1.5.1字典序法由中介数推出排列的算法[例]由72642321推算出839647521方法1：P1P2P3P4P5P6P7P8P9_________P1=88→7+1=82+1=3→P2=336+1=7，但3已在P3左边出现，↑7+1=8，但8已在P3左边出现，↑8+1=9→P3=994+1=5，但3已经在P4左边出现，5+1=6→P4=66↑2+1=3，但3已经在P5左边出现，3+1=4→P4=443+1=4，但3,4已经在P6左边出现，4+1+1=6，但6已经在P6左边出现，6+1=7→P6=772+1=3，但3已经在P7左边出现，3+1=4，但4已经在P7左边出现，4+1=5→P7=551+1=2→P8=2→P9=121这个过程比较麻烦(这酝酿着改进的可能)，该算法从左到右依次推出P1,P2,…,P9。下述算法依次定出1,2,3,…,9的位置。[e-mail]1.5.1字典序法方法2-1：72642321中未出现0，1在最右边中介数右端加一个0扩成9位，先定1，每定一位，其左边未定位下加一点，从（位－位下点数=0）的位中选最左的。726423210定1的位置1●●●●●●●●22●●●●●●●33●44●●●55●●●●66●●77●●8899由72642321推算出[e-mail]1.5.1字典序法方法2-2：已定出上标‘●’，找左起第一个0，下标‘__’由72642321推算出839647521●72642321-11111111=61531210________12●●●●61531210-11111110=504201003●●●●50420100-10000000=404201004●●●●●40420100-10110000=303101005●●●●●●●●30310100-10110100=202000006●●●●●●●●●●20200000-10100000=101000007●●●●●●●●●●●●10100000-10100000=000000008●●●●●●●000000009以上两种从中介数求排列的算法都比较麻烦。给定一排列与下一个排列各自的中介数→进位链（中介数的后继）→递增进位制数[e-mail]1.5.2递增进位制数法1)由排列求中介数在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2—n)一致。1.5.2递增进位制数法可看出n-1位的进位链。右端位逢2进1，右起第2位逢3进1，…，右起第i位逢i+1进1，i=1,2,…,n-1.这样的中介数我们称为递增进位制数。上面是由中介数求排列。[e-mail]1.5.2递增进位制数法由序号（十进制数）求中介数（递增进位制数）如下：m=m1,0≤m≤n!-1m1=2m2+kn-1,0≤kn-1≤1m2=3m3+kn-2,0≤kn-2≤2…………….mn-2=(n-1)mn-1+k2,0≤k2≤n-2mn-1=k1,0≤k1≤n-1p1p2…pn←→(k1k2…kn-1)↑←→[e-mail]1.5.2递增进位制数法在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。为方便起见，令ai+1=kn-I，i=1,2,…,n-1(k1k2…kn-1)↑=(anan-1…a2)↑ai：i的右边比i小的数字的个数[e-mail]1.5.2递增进位制数法在这样的定义下，有839647521←→(67342221)↑(67342221)↑+1=(67342300)↑←→8496175236×8+7)×7+3)×6+4)×5+2)×4+2)×3+2)×2+1=[e-mail]1.5.2递增进位制数法由(anan-1…a2)↑求p1p2…pn。从大到小求出n,n-1,…,2,1的位置_..._n__…_an个空格n的右边有an个空格。n-1的右边有an-1个空格。…………2的右边有a2个空格。最后一个空格就是1的位置。\____________/[e-mail]1.5.2递增进位制数法_________67342221↓↓↓↓↓↓↓↓a9a8a7a6a5a4a3a2★\____________________/V6个空格9★\____________________________/V7个空格8★★★★★★\________/V3个空格765431\________________/V4个空格\____/V2个空格1个空格序号nm=∑ak(k-1)!k=[e-mail]1.5.3递减进位制数法在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。(anan-1…a2)↑→(a2a3…an-1an)↓839647521→(12224376)↓nnm=∑akn!/k!=n!∑ak/k!k=2k=2(12224376)↓=1×3+2)×4+2)×5+2)×6+4)×7+3)×8+7)×9+6=340989※※求下一个排列十分容易[e-mail]1.5.4邻位对换法递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左，而邻位对换法的换位是双向的。[e-mail]1.5.4邻位对换法这个算法可描述如下：对1—n-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1—n的n个排列。对1—n-