全排列的生成算法对于给左的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。
字典序法按照字典序求下一个排列的算法广例字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是：123,132,213,231,312,321o注意一个全排列可看做一个字符串，字符串可有前缀、后缀/生成给泄全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。
这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
广例839647521是1—9的排列。
1—9的排列最前而的是123456789,最后而的是987654321,从右向左扫描若都是增的，就到了987654321,也就没有下一个了。
否则找出第一次出现下降的位置。
算法：由P1P2...Pn生成的下一个排列的算法如下：1求j=max{j| Pj-I<pj}2.求|=max{k| Pi-1<Pk }3.交换Pi-1与PI得到P1P2...PI-1 （P i....Pn ）,将红色部分顺序逆转，得到结果.例求839647521的下一个排列1.确定i,从左到右两两比较找出后一个数比前一个大的组合，在这里有39 47,然后i 取这些组中最到的位宜号（不是最大的数）在这两组数中7的位置号最大为6,所以i=62.确立I.找岀在i （包括i）后面的所有比i前面那一位大的数的最大的位置号，在此例中7, 5都满足要求，则选5, 5的位置号为7,所以1=73.先将4和5交换，然后将5后的四位数倒转得到结果8396574213 839651247以上算法是在数论课上老师给岀的关于字典序全排列的生成算法，以前也经常要用到全排列生成算法来生成一个全排列对所有的情况进行测试，每次都是现到网上找一个算法，然后直接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 o字典序算法如下：设P是1~n的一个全排列:p=p1p2……pn=plp2……pj-lpjpj+1……pk-1pkpk+1……pn1) 从排列的右端开始，找出第一个比右边数字小的数字的序号j (j从左端开始il•算)，即j=max{i|pi<pi+1}2) 在pj的右边的数字中，找出所有比pj大的数中报小的数字pk.即k=max{i|pi>pj}(右边的数从右至左是递増的•因此k是所有大干pj的数字中序号最大者)3) 对换pi. pk4) 再将pj+1……pk-lpkpk+lpn倒转得到排列p=plp2••…pj-lpjpn••…pk+1pkpk-1••…pj+1,这就是排列p的下一个下一个排列。
例如839647521是数字1〜9的一个排列。
从它生成下一个排列的步骤如下：自右至左找出排列中第一个比右边数字小的数字4 839647521在该数字后的数字中找出比4大的数中最小的一个5 839647521将5与4交换839657421将7421 倒转839651247所以839647521的下一个排列是839651247。
程序代码如下：Private Sub Dict(p() As Integer, ByVai n As Integer)Dim i As Integer, j As IntegerOutL pi = n -1Do While i > 0If p(i) < p(i + 1) ThenFor j = n To i + 1 Step -1 •从排列右端开始If p(i) <= p(j) Then Exit For ■找出递减子序列i = i + 1NextSwap p(i)t p(j) ■将递减子序列前的数字与序列中比它大的第一个数交换For j = n To 1 Step -1•将这部分排列倒转If i >= j Then Exit ForSwap p(i), p(j)NextOutLp '输出一个排列1 = nEnd Ifi = i -1LoopEnd SubSwap p(i)t p(j)是交换两个元素的子过程.OWL p是输出排列的子过程。
2 •递增进位数制法在递增进位制数法中.从一个排列求另一个排列需雯用到中介数。
如果用ki表示排列plp2...pi...pn中元素pi的右边比pi 小的数的个数.则排列的中介数就是对应的排列ki……ki……kn-l o例如排列839647521的中介数是72642321, 7、2、6 .................分别是排列中数字& 3、9 ................ 的右边比它小的数字个数。
中介数是计算排列的中间环节。
已知一个排列，要求下一个排列，首先确定其中介数.一个排列的后继.其中介数是原排列中介数加仁需要注意的是,如果中介数的末位kn-1+1=2.则要向前进位，一般情形,如果ki+1=n-i+1,则要进位，这就是所谓的递增进位制。
例如排列839647521的中介数是72642321,则下一个排列的中介数是67342221+1=67342300(W为1+1=2,所以向前进位.2+1=3,又发生进位，所以下一个中介数是67342300)。
得到中介数后，可根据它还原对应得排列。
算法如下：中介数k1、k2 ............ kn-1的各位数字顺序表示排列中的数字n、.............. 2在排列中距右端的的空位数•因此，要按k仁k2 ................ kn-1的值从右向左确定n. n-1 .................. 2的位宜•并逐个放置在排列中：i放在右起的ki+1位，如果某位已放有数字，则该位宜不算在内，最后一个空位放仁因此从67342300可得到排列849617523,它就是839647521的后一个排列。
因为9最先放宜,k1=6, 9 放在右起第7位.空出6个空位.然后是放8, k2=7, 8放在右起第8位，但9占用一位，故8应放在右起第9位.余类推。
程序代码如下：Private Sub lncr(p() As Integer, ByVai n As Integer)Dim m() As Integer '保存中介数的数组Dim i As Integer, j As IntegerDim a As IntegerReDim m(n)For i = 1 To n'第一个排列的中介数为000 0i = i + 1For i = 1 To n -1 '计算中介数各位之和•将数字i 放宜在指定位置Next OutLpIf MedN(m) Then Exit Do •汁算下一个中介数，如果是00..0 则全部排列找到Loop End SubPrivate Function MedN(m() As lnteger)As Boolean Dim i As Integer, sum As Integer Dim b As Boolean b = FalseDo While i > 0 m(i) = m(i) + 1If m(i) < n - i + 1 Then Exit Do m(i) = 0 i = i -1 Loop Sum = 0m(i) = 0 NextDo While n > 0 Fori = 1 To n •排列的各位为0P(i) = 0 Next Fori = 1 To n '从右向左察看排列中为0的位 a = m(i) + 1Do While j > 0 If p(j) = 0 ThenIf a = 0 Then Exit Do •0的个数决定数字i 的位宜End IfLoopp(j) = n - i + 1 •讣算中介数函数i = i + 1Sum = Sum + m(i) NextIf Sum = 0 Then b = True MedN = b End Function 3 •递减进位制数法在递増进位制数法中•中介数的最低位是逢2进仁进位频繁.这是一个缺点。
把递增进位制数翻转,就得到 递减进位制数c839647521的中介数是67342221(k1k2...kn-1),倒转成为12224376(kn-1...k2k1),这是递减进位制数的中 介数：ki(i=n-1,n-2,...,2)fe 逢i 向ki-1位进给定排列p, p 的下一个排列的中介数定义为p 的中介数加 例如p=839647521, p 的中介数为12224376, p 的下一个排列的中介数为12224376+1=12224377.由此 得到p 的下一个排列为893647521。
给定中介数.可用与递增进位制数法类似的方法还原出排列。
但在递减进位制数中，可以不先计算中介数就 直接从一个排列求出下一个排列。
具体算法如下：1) 如果p(i)=n 且iv>n,则p(i)与p(i ・l)交换2) 如果p(n)=n.则找出一个连续递减序列9、8 ................... i,将其从排列左端删除，再以相反顺序加在排列右端，然后将PI 与左边的数字交换例如p=893647521的下一个排列是98364752仁 求983647521的下一个排列时•因为9在最左边且第2位 为&第3位不是7,所以将8和9从小到大排于最右端364752189,再将7与其左方数字对调得到983647521 的下一个排列是367452189。