全排列生成算法

全排列的生成算法对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。字典序法按照字典序求下一个排列的算法/*例字符集{1,2,3}，较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。注意一个全排列可看做一个字符串，字符串可有前缀、后缀。*/生成给定全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。/*例是1—9的排列。1—9的排列最前面的是，最后面的是，从右向左扫描若都是增的，就到了，也就没有下一个了。否则找出第一次出现下降的位置。算法：由P1P2."n生成的下一个排列的算法如下:1.求i=max{j|Pj-1<Pj}2.求l=max{k|Pi-1<Pk}3.交换Pi-1与Pl得到P1P2...Pi-1（Pi....Pn）,将红色部分顺序逆转，得到结果.例求的下一个排列1.确定i，从左到右两两比较找出后一个数比前一个大的组合，在这里有3947,然后i取这些组中最到的位置号（不是最大的数）在这两组数中7的位置号最大为6,所以』62.确定l，找出在i（包括i）后面的所有比i前面那一位大的数的最大的位置号，在此例中7,5都满足要求，则选5,5的位置号为7,所以l=73.先将4和5交换，然后将5后的四位数倒转得到结果a以上算法是在数论课上老师给出的关于字典序全排列的生成算法，以前也经常要用到全排列生成算法来生成一个全排列对所有的情况进行测试，每次都是现到网上找一个算法，然后直接copy代码，修改一下和自己的程序兼容就行了，也不看是怎么来的，不是我不想看，实在是说的很抽象，那一大堆公式来吓人，一个实例都不给，更有甚者连算法都没有，只是在那里说，想看都看不懂，也没那个耐心取理解那些人写出来的那种让人无法忍受的解释。不过在说别人的同时我也知道，自己写的也不够好，不过这就是我的理解了，没法子写的再细了。全排列的生成算法2008年04月25日星期五下午03:23全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1〜n的n个数字的排列一一对应，因此在此就以n个数字的排列为例说明排列的生成法。n个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从它的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。全排列的生成法通常有以下几种：字典序法递增进位数制法递减进位数制法邻位交换法n进位制法递归类算法字典序法字典序法中，对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列12354和12345,排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345,最后面的是54321。字典序算法如下：设P是1〜n的一个全排列:p=p1p2 pn=p1p2 pj-1pjpj+1 pk-1pkpk+1 pn从排列的右端开始，找出第一个比右边数字小的数字的序号j(j从左端开始计算)，即j=max{i|pi<pi+1}在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即k=max{i|pi>pj}(右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者)对换pi，pk再将pj+1……pk-1pkpk+1pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个下一个排列。例如是数字1〜9的一个排列。从它生成下一个排列的步骤如下：自右至左找出排列中第一个比右边数字小的数字4在该数字后的数字中找出比4大的数中最小的一个5将5与4交换将7421倒转所以的下一个排列是。程序代码如下：PrivateSubDict(p()AsInteger,ByValnAsInteger)DimiAsInteger,jAsIntegerOutLpi=n-1DoWhilei>0Ifp(i)<p(i+1)ThenForj=nToi+1Step-1 '从排列右端开始Ifp(i)<=p(j)ThenExitFor '找出递减子序列NextSwapp(i),p(j) '将递减子序列前的数字与序列中比它大的第一个数交换Forj=nTo1Step-1 '将这部分排列倒转i=i+1Ifi>=jThenExitForSwapp(i),p(j)NextOutLp '输出一个排列i=nEndIfi=i-1LoopEndSubSwapp(i),p(j)是交换两个元素的子过程，OutLp是输出排列的子过程。递增进位数制法在递增进位制数法中，从一个排列求另一个排列需要用到中介数。如果用ki表示排列p1p2...pi...pn中元素pi的右边比pi小的数的个数，则排列的中介数就是对应的排列k1......ki......kn-1。例如排列的中介数是，7、2、6 分别是排列中数字8、3、9 的右边比它小的数字个数。中介数是计算排列的中间环节。巳知一个排列，要求下一个排列，首先确定其中介数，一个排列的后继，其中介数是原排列中介数加1,需要注意的是，如果中介数的末位kn-1+1=2，则要向前进位，一般情形，如果ki+1=n-i+1,则要进位，这就是所谓的递增进位制。例如排列的中介数是，则下一个排列的中介数是+1=(因为1+1=2,所以向前进位，2+1=3，又发生进位，所以下一个中介数是)。得到中介数后，可根据它还原对应得排列。算法如下：中介数k1、k2 kn-1的各位数字顺序表示排列中的数字n、n-1 2在排列中距右端的的空位数，因此，要按k1、k2 kn-1的值从右向左确定n、n-1 2的位置，并逐个放置在排列中：i放在右起的ki+1位，如果某位巳放有数字，则该位置不算在内，最后一个空位放1。因此从可得到排列，它就是的后一个排列。因为9最先放置，k1=6,9放在右起第7位，空出6个空位，然后是放8,k2=7,8放在右起第8位，但9占用一位，故8应放在右起第9位，余类推。程序代码如下：PrivateSubIncr(p()AsInteger,ByValnAsInteger)Dimm()AsInteger '保存中介数的数组DimiAsInteger,jAsIntegerDimaAsIntegerReDimm(n)Fori=1Ton '第一个排列的中介数为000......0m(i)=0NextDoWhilen>0p(i)=0NextFori=1Ton'从右向左察看排列中为0的位a=m(i)+1DoWhilej>0Ifp(j)=0ThenIfa=0ThenExitDo'0的个数决定数字i的位置EndIfLoopp(j)=n-i+1'将数字i放置在指定位置NextOutLpIfMedN(m)ThenExitDo p(i)=0NextFori=1Ton'从右向左察看排列中为0的位a=m(i)+1DoWhilej>0Ifp(j)=0ThenIfa=0ThenExitDo'0的个数决定数字i的位置EndIfLoopp(j)=n-i+1'将数字i放置在指定位置NextOutLpIfMedN(m)ThenExitDo '计算下一个中介数，如果是00...0，则全部排列找到LoopEndSubPrivateFunctionMedN(m()AsInteger)AsBoolean'计算中介数函数DimiAsInteger,sumAsIntegerDimbAsBooleanb=FalseDoWhilei>0m(i)=m(i)+1Ifm(i)<n-i+1ThenExitDom(i)=0LoopSum=0Fori=1Ton-1'计算中介数各位之和Sum=Sum+m(i)NextIfSum=0Thenb=True'中介数各位之和为0MedN=bEndFunction递减进位制数法在递增进位制数法中，中介数的最低位是逢2进1,进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。的中介数是(k1k2...kn-1)ki-1位进1。给定排列p，倒转成为(kn-1...k2k1)，的中介数是(k1k2...kn-1)ki-1位进1。给定排列p，p的下一个排列的中介数定义为p的中介数加1。例如p=，p的中介数为，p的下一个排列的中介数为+1=一个排列的中介数为+1=由此得到p的下一个排列为。给定中介数，可用与递增进位制数法类似的方法还原出排列。但在递减进位制数中，可以不先计算中介数就直接从一个排列求出下一个排列。具体算法如下:1)如果p(i)=n且i<>n，则p(i)与p(i-1)交换2)如果2)如果p(n)=n，则找出一个连续递减序列9、8、、i，将其从排列左端删除，再以相反顺序加在排列右端，然后将i-1与左边的数字交换例如p=的下一个排列是。求的下一个排列时，因为9在最左边且第2位为8,第3位不是7,所以将8和9从小到大排于最右端，再将7与其左方数字对调得到的下一个排列是。又例如求的下一个排列，只需要将端，然后将i-1与左边的数字交换例如p=的下一个排列是。求的下一个排列时，因为9在最左边且第2位为8,第3位不是7,所以将8和9从小到大排于最右端，再将7与其左方数字对调得到的下一个排列是。又例如求的下一个排列，只需要将9876从小到大排到最右端并将5与其左方数字3对调，得到。程序代码如下:PrivateSubDegr(p()AsInteger,ByValnAsInteger)DimiAsInteger,jAsIntegerDoWhilen>0OutLpIfp(1)=nThen'如果第一位是nDo'从左端开始找出最长的连续递降序列Ifi=nThenExitSubLoopUntilp(i)<>p(i+1)+1Do'找出递降序列末尾数字的下一个数字LoopUntilp(i)=p(j)-1Swapp(i),p(i-1)'将它与序列末尾数字交换Fori=1Ton-j'将递减序列倒转后放置在排列右端p(i)=p(i+j)Nextp(n-i+1)=n-p(n-i+1)=n-i+1NextElse'如果最高位不是n'从左端开始Do'找出n所在位置LoopUntilp(i)=nSwapp(i),p(i-Swapp(i),p(i-1)'将n与其左边数字交换EndIfLoopEndSub邻位对换法邻位对换法中下一个排列总是上一个排列某相邻两位对换得到的。以4个元素的排列为例，将最后的元素4逐次与前面的元素交换，可以生成4个新排列：1234124314234123然后将最后一个排列的末尾的两个元素交换，再逐次将排头的4与其后的元素交换，又生成四个新排列：4132143213421324再将最后一个排列的末尾的两个元素交换，将4从后往前移：3124314234124312如此循环既可求出全部排列。程序代码如下：PrivateSubAdja(p()AsInteger,ByValnAsInteger)m=1Fori=3Ton-1 '计算(n-1)!/2m=m*iNextFori=1Tom-1OutLpForj=nTo2Step-1'Forj=nTo2Step-1'将n从排列尾逐位向前移Swapp(j),p(j-1)OutLp'移动一次产生一个新排列OutLpNextSwapp(n),p(n-1)OutLp

Forj=1Ton-1 '将n从排列头逐位向后移Swapp(j),p(j+1)OutLp '移动一次产生一个新排列NextSwapp(1),p(2)NextEndSub元素增值法(n进制法)从原始排列p=p1p2......pn开始，第n位加n-1,如果该位的值超过n，则将它除以n，用余数取代该位，并进位(将第n-1位加1)再按同样方法处理n-1位，n-2位，......，直至不再发生进位为止，处理完一个排列就产生了一个新的排列将其中有相同元素的排列去掉当第一个元素的值〉n则结束以3个数1、2、3的排列为例：原始排列是123,从它开始，第3个元素是3,3+2=5,5Mod3=2，第2个元素是2,2+1=3,所以新排列是132。通过元素增值，顺序产生的排列是：123,132,211,213,222,231,233,312,321有下划线的排列中存在重复元素，丢弃，余下的就是全部排列。PrivateSubIncr(p()AsInteger,ByValnAsInteger)DimiAsInteger,jAsIntegerDoWhilen>0OutLp'第n个元素增值n-1'从后往前检查'第n个元素增值n-1'从后往前检查'如果元素增值后超过n'用n除它取余数'向前一个元素进位'第一个元素值超过n,则所有排列都找到'检查排列中的元素是否重复Forj=nTo2Step-1Ifp(j)>nThenp(j)=p(j)Modnp(j-1)=p(j-1)+1Ifp(1)>nThenExitSubEndIfNextFori=1Ton-1Forj=i+1TonIfp(i)=p(j)ThenGoToNextn'排列中有重复元素，丢弃Next

LoopEndSub递归类算法全排列的生成方法用递归方式描述比较简洁，实现的方法也有多种。1）回溯法回溯法通常是构造一颗生成树。以3个元素为例；树的节点有个数据，可取值是1、2、3。如果某个为0，则表示尚未取值。初始状态是（0，0，0），第1个元素值可以分别挑选1,2,3,因此扩展出3个子结点。用相同方法找出这些结点的第2个元素的可能值，如此反复进行，一旦出现新结点的3个数据全非零，那就找到了一种全排列方案。当尝试了所有可能方案，即获得了问题的解答。程序代码如下：PrivateSubRemo(p()AsInteger,ByValkAsInteger)DimbAsBooleanIfk=n+1ThenOutLpDimbAsBooleanIfk=n+1ThenOutLpElseFori=1Tonb=Falsep(k)=iForj=1Tok-1Ifi=p(j)Thenb=Truej=k-1EndIfNextIfNotbThenRemo,k+1NextEndIf'否则'重复元素标志置为False'第k个元素设为i'检查是否存在重复元素'有重复'设置重复标志为True'回溯'换一个元素试探'无重复，继续递归找下一个元素EndSub2）递归算法如果用P表示n个元素的排列，而Pi表示不包含元素i的排列，（i）Pi表示在排列Pi前加上前缀i的排列，那么，n个元素的排列可递