全排列的生成算法:字典序法
???全排列的生成算法?對于給定的字符集，用有效的方法將所有可能的全排列無重復無遺漏地枚舉出來。? ???字典序法按照字典序求下一個排列的算法?生成給定全排列的下一個排列所謂一個全排列的下一個排列就是這一個排列與下一個排列之間沒有其他的排列。這就要求這一個排列與下一個排列有盡可能長的共同前綴，也即變化限制在盡可能短的后綴上。 ???/*例?839647521是1—9的排列。1—9的排列最前面的是123456789，最后面的是987654321，從右向左掃描若都是增的，就到了987654321，也就沒有下一個了。否則找出第一次出現下降的位置。 ???算法: 由 P1P2…Pn 生成的下一個排列的算法如下: ???1. 求 i=max{j| Pj-1 ???2. 求 l=max{k| Pi-1 ???3.?交換Pi-1 與Pl得到P1P2…Pi-1 (P i....Pn ) , 將紅色部分順序逆轉,得到結果.? ???例?求839647521的下一個排列 ???1. 確定i，從左到右兩兩比較找出后一個數比前一個大的組合，在這里有39 47，然后i取這些組中最到的位置號（不是最大的數）在這兩組數中7的位置號最大為6，所以i=62.確定l， 找出在i（包括i）后面的所有比i前面那一位大的數的最大的位置號，在此例中7，5 都滿足要求，則選5，5的位置號為7，所以?l=73. 先將4和5交換，然后將5后的四位數倒轉得到結果 ????????839657421à?839651247 ????以上算法是在數論課上老師給出的關于字典序全排列的生成算法，以前也經常要用到全排列生成算法來生成一個全排列對所有的情況進行測試，每次都是現到網上找一個算法，然后直接copy代碼，修改一下和自己的程序兼容就行了，也不看是怎么來的，不是我不想看，實在是說的很抽象，那一大堆公式來嚇人，一個實例都不給，更有甚者連算法都沒有，只是在那里說，想看都看不懂，也沒那個耐心取理解那些人寫出來的那種讓人無法忍受的解釋。不過在說別人的同時我也知道，自己寫的也不夠好，不過這就是我的理解了，沒法子寫的再細了。


全排列的生成算法

????全排列的生成算法就是對于給定的字符集，用有效的方法將所有可能的全排列無重復無遺漏地枚舉出來。任何n個字符集的排列都可以與1～n的n個數字的排列一一對應，因此在此就以n個數字的排列為例說明排列的生成法。
????n個字符的全體排列之間存在一個確定的線性順序關系。所有的排列中除最后一個排列外，都有一個后繼；除第一個排列外，都有一個前驅。每個排列的后繼都可以從 它 的前驅經過最少的變化而得到，全排列的生成算法就是從第一個排列開始逐個生成所有的排列的方法。
????全排列的生成法通常有以下幾種：
字典序法
遞增進位數制法
遞減進位數制法
鄰位交換法
n進位制法
遞歸類算法

1.字典序法
????字典序法中，對于數字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
1）從排列的右端開始，找出第一個比右邊數字小的數字的序號j（j從左端開始計算），即???j=max{i|pi
2）在pj的右邊的數字中，找出所有比pj大的數中最小的數字pk，即 k=max{i|pi>pj}（右邊的數從右至左是遞增的，因此k是所有大于pj的數字中序號最大者）
3）對換pi，pk
4）再將pj+1......pk-1pkpk+1pn倒轉得到排列p'=p1p2.....pj-1pjpn.....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, ByVal n As Integer)
Dim i As Integer, j As Integer
OutL p
i = n - 1
Do While i > 0
???If p(i) < p(i + 1) Then
For j = n To i + 1 Step -1 ?????????????????????????'從排列右端開始
If p(i) <= p(j) Then Exit For ???????????????'找出遞減子序列
Next
Swap p(i), p(j) ??????????????????'將遞減子序列前的數字與序列中比它大的第一個數交換
For j = n To 1 Step -1 ???????????????????????????'將這部分排列倒轉
i = i + 1
If i >= j Then Exit For
Swap p(i), p(j)
Next
OutL p ????????????????????????????????????????????????????'輸出一個排列
i = n
???End If
???i = i - 1
Loop
End Sub
Swap p(i), p(j)是交換兩個元素的子過程，OutL p是輸出排列的子過程。

2.遞增進位數制法
????在遞增進位制數法中，從一個排列求另一個排列需要用到中介數。如果用 ki表示排列p1p2...pi...pn中元素pi的右邊比pi小的數的個數，則排列的中介數就是對應的排列k1 ...... ki...... kn-1。
例如排列839647521的中介數是72642321，7、2、6、......分別是排列中數字8、3、9、......的右邊比它小的數字個數。
中介數是計算排列的中間環節。已知一個排列，要求下一個排列，首先確定其中介數，一個排列的后繼，其中介數是原排列中介數加1，需要注意的是，如果中介數 的末位kn-1+1=2，則要向前進位，一般情形，如果ki+1=n-i+1，則要進位，這就是所謂的遞增進位制。例如排列839647521的中介數是 72642321，則下一個排列的中介數是67342221+1=67342300（因為1+1=2，所以向前進位，2+1=3，又發生進位，所以下一個 中介數是67342300）。
得到中介數后，可根據它還原對應得排列。算法如下：
中介數k1、k2、......、kn-1的各位數字順序表示排列中的數字n、n-1、......、2在排列中距右端的的空位數，因此，要按k1、 k2、......、kn-1的值從右向左確定n、n-1、......、2的位置，并逐個放置在排列中：i放在右起的ki+1位，如果某位已放有數字， 則該位置不算在內，最后一個空位放1。
因此從67342300可得到排列849617523，它就是839647521的后一個排列。因為9最先放置，k1=6，9放在右起第7位，空出6個空位，然后是放8，k2=7，8放在右起第8位，但9占用一位，故8應放在右起第9位，余類推。
程序代碼如下：

Private Sub Incr(p() As Integer, ByVal n As Integer)
Dim m() As Integer ??????????????????????????????'保存中介數的數組
Dim i As Integer, j As Integer
Dim a As Integer
ReDim m(n)
For i = 1 To n ???????????????????????????????????????'第一個排列的中介數為000......0
???m(i) = 0
Next
Do While n > 0
???For i = 1 To n ???????????????????????????????????????'排列的各位為0
p(i) = 0
???Next
???For i = 1 To n ???????????????????????????????????????'從右向左察看排列中為0的位
a = m(i) + 1
j = n
Do While j > 0
If p(j) = 0 Then
????a = a - 1
????If a = 0 Then Exit Do ?????????????????????'0的個數決定數字i的位置
End If
j = j - 1
Loop
p(j) = n - i + 1 ????????????????????????????????????'將數字i放置在指定位置
???Next ?????????????????
???OutL p
???If MedN(m) Then Exit Do ??????'計算下一個中介數，如果是00...0，則全部排列找到
Loop
End Sub
Private Function MedN(m() As Integer)As Boolean ???????'計算中介數函數
Dim i As Integer, sum As Integer
Dim b As Boolean
b = False
i = n - 1
Do While i > 0 ????????????????????????????????????????????????????????
???m(i) = m(i) + 1
???If m(i) < n - i + 1 Then Exit Do
???m(i) = 0
???i = i - 1
Loop
Sum = 0
For i = 1 To n - 1 ??????????????????????????????'計算中介數各位之和
???Sum = Sum + m(i)
Next
If Sum = 0 Then b = True ???????????????????'中介數各位之和為0
MedN = b
End Function

3.遞減進位制數法
在遞增進位制數法中，中介數的最低位是逢2進1，進位頻繁，這是一個缺點。把遞增進位制數翻轉,就得到遞減進位制數。
839647521的中介數是67342221(k1k2…kn-1)，倒轉成為12224376(kn-1…k2k1)，這是遞減進位制數的中介數： ki(i=n-1,n-2,…,2)位逢i向ki-1位進1。給定排列p，p的下一個排列的中介數定義為p的中介數加1。例如p=839647521，p 的中介數為12224376，p的下一個排列的中介數為12224376+1=12224377，由此得到p的下一個排列為893647521。
給定中介數，可用與遞增進位制數法類似的方法還原出排列。但在遞減進位制數中，可以不先計算中介數就直接從一個排列求出下一個排列。具體算法如下：
1）如果p(i)=n且i<>n，則p(i)與p(i-1)交換
2）如果p(n)=n，則找出一個連續遞減序列9、8、......、i，將其從排列左端刪除，再以相反順序加在排列右端，然后將i-1與左邊的數字交換

例如p=893647521的下一個排列是983647521。求983647521的下一個排列時，因為9在最左邊且第2位為8，第3位不是7，所以將 8和9從小到大排于最右端364752189，再將7與其左方數字對調得到983647521的下一個排列是367452189。又例如求 987635421的下一個排列，只需要將9876從小到大排到最右端并將5與其左方數字3對調，得到534216789。
程序代碼如下：
Private Sub Degr(p() As Integer, ByVal n As Integer)
Dim i As Integer, j As Integer
Do While n > 0
???OutL p
???If p(1) = n Then ??????????????????????????????'如果第一位是n
i = 0
Do ????????????????????????????????????????????????????'從左端開始找出最長的連續遞降序列
i = i + 1
If i = n Then Exit Sub
Loop Until p(i) <> p(i + 1) + 1
j = i
Do ????????????????????????????????????????????????'找出遞降序列末尾數字的下一個數字
i = i + 1
Loop Until p(i) = p(j) - 1
Swap p(i), p(i - 1) ????????????????????????'將它與序列末尾數字交換
For i = 1 To n - j ????????????????????????????'將遞減序列倒轉后放置在排列右端
p(i) = p(i + j)
Next
For i = 1 To j
p(n - i + 1) = n - i + 1
Next
???Else ?????????????????????????????????????????????????'如果最高位不是n
i = 0 ?????????????????????????????????????????????'從左端開始
Do ????????????????????????????????????????????????'找出n所在位置
i = i + 1
Loop Until p(i) = n
Swap p(i), p(i - 1) ?????????????????????????'將n與其左邊數字交換
???End If
Loop
End Sub

?

4.鄰位對換法
????鄰位對換法中下一個排列總是上一個排列某相鄰兩位對換得到的。以4個元素的排列為例，將最后的元素4逐次與前面的元素交換，可以生成4個新排列：
1 2 3 4???1 2 4 3???1 4 2 3???4 1 2 3
????然后將最后一個排列的末尾的兩個元素交換，再逐次將排頭的4與其后的元素交換，又生成四個新排列：
???4 1 3 2???1 4 3 2???1 3 4 2???1 3 2 4
????再將最后一個排列的末尾的兩個元素交換，將4從后往前移：
3 1 2 4???3 1 4 2???3 4 1 2 4 3 1 2
????如此循環既可求出全部排列。
????程序代碼如下：
Private Sub Adja(p() As Integer, ByVal n As Integer)
m = 1
For i = 3 To n - 1 ???????????????????????????????'計算(n-1)!/2
???m = m * i
Next
For i = 1 To m - 1 ??????????????????????????
???OutL p
???For j = n To 2 Step -1 ?????????????????????'將n從排列尾逐位向前移
Swap p(j), p(j - 1)
OutL p ??????????????????????????????????????????'移動一次產生一個新排列
???Next
???Swap p(n), p(n - 1) ???????????????????????
???OutL p
???For j = 1 To n - 1 ???????????????????????????'將n從排列頭逐位向后移
Swap p(j), p(j + 1)
OutL p ??????????????????????????????????????????'移動一次產生一個新排列
???Next
???Swap p(1), p(2)
Next
End Sub??

5.元素增值法（n進制法）
1）從原始排列p=p1p2......pn開始，第n位加n-1，如果該位的值超過n，則將它除以n，用余數取代該位，并進位（將第n-1位加1）
2）再按同樣方法處理n-1位，n-2位，......，直至不再發生進位為止，處理完一個排列就產生了一個新的排列
3）將其中有相同元素的排列去掉
4）當第一個元素的值>n則結束
????以3個數1、2、3的排列為例：原始排列是1???2???3，從它開始，第3個元素是3，3+2=5，5 Mod 3=2，第2個元素是2，2+1=3，所以新排列是1 3 2。通過元素增值，順序產生的排列是：1???2???3，1???3???2，2???1???1，2???1??3，2???2???2，2???3???1，2???3???3，3???1???2，3???2???1
????有下劃線的排列中存在重復元素，丟棄，余下的就是全部排列。
Private Sub Incr(p() As Integer, ByVal n As Integer)
???Dim i As Integer, j As Integer ????????????????????????????????????????????
???Do While n > 0
OutL p
Nextn:???p(n) = p(n) + n - 1 ???????????????'第n個元素增值n-1
???For j = n To 2 Step -1 ??????????????????????'從后往前檢查
If p(j) > n Then ???????????????????????????????'如果元素增值后超過n
p(j) = p(j) Mod n ????????????????????????????'用n除它取余數
p(j - 1) = p(j - 1) + 1 ??????????????????????'向前一個元素進位
If p(1) > n Then Exit Sub ????????????'第一個元素值超過n，則所有排列都找到
End If
???Next
???For i = 1 To n - 1 ????????????????????????????'檢查排列中的元素是否重復
For j = i + 1 To n
If p(i) = p(j) Then GoTo Nextn '排列中有重復元素，丟棄
Next
???Next
Loop
End Sub

6.遞歸類算法
?全排列的生成方法用遞歸方式描述比較簡潔，實現的方法也有多種。
1）回溯法
回溯法通常是構造一顆生成樹。以3個元素為例；樹的節點有個數據，可取值是1、2、3。如果某個為0，則表示尚未取值。
初始狀態是(0，0，0)，第1個元素值可以分別挑選1，2，3，因此擴展出3個子結點。用相同方法找出這些結點的第2個元素的可能值，如此反復進行，一旦出現新結點的3個數據全非零，那就找到了一種全排列方案。當嘗試了所有可能方案，即獲得了問題的解答。
程序代碼如下：
Private Sub Remo(p() As Integer, ByVal k As Integer)
???Dim b As Boolean
???If k = n + 1 Then ???????????????????????????'如果k>n則輸出一個排列??
OutL p
???Else ????????????????????????????????????????????????'否則
For i = 1 To n ????????????
????b = False ???????????????????????????????????????'重復元素標志置為False
p(k) = i ??????????????????????????????????????????'第k個元素設為i
For j = 1 To k - 1 ???????????????????????????'檢查是否存在重復元素
???If i = p(j) Then ???????????????????????????????'有重復
???b = True ???????????????????????????????????????'設置重復標志為True
???j = k - 1 ???????????????????????????????????????'回溯
End If
Next ????????????????????????????????????????????????'換一個元素試探
If Not b Then Remo, k + 1 ????????????'無重復，繼續遞歸找下一個元素
???Next
End If
End Sub
2）遞歸算法
如果用P表示n個元素的排列，而Pi表示不包含元素i的排列，(i)Pi表示在排列Pi前加上前綴i的排列，那么，n個元素的排列可遞歸定義為：
如果n=1，則排列P只有一個元素i
如果n>1，則排列P由排列(i)Pi構成（i=1、2、....、n-1）。
根據定義，容易看出如果已經生成了k-1個元素的排列，那么，k個元素的排列可以在每個k-1個元素的排列Pi前添加元素i而生成。例如2個元素的排列是 1???2和2 1，對與個元素而言，p1是2???3和3???2，在每個排列前加上1即生成1 2 3和1 3 2兩個新排列，p2和p3則是1???3、3???1和1???2、2???1，按同樣方法可生成新排列2 1 3、2 3 1和3 1 2、3 2 1。
程序代碼如下：
Private Sub Recu(p() As Integer, ByVal k As Integer)
???If k = n Then
OutL p
???Else
For i = k To n
???Swap p(k), p(i)
???Recu p, k + 1
???Swap p(k), p(i)
Next
???End If
End Sub

3）循環移位法
????如果已經生成了k-1個元素的排列，則在每個排列后添加元素k使之成為k個元素的排列，然后將每個排列循環左移（右移），每移動一次就產生一個新的排列。
????例如2個元素的排列是1 2和2 1。在1 2 后加上3成為新排列1 2 3，將它循環左移可再生成新排列2 3 1、3 1 2，同樣2 1 可生成新排列2 1 3、1 3 2和3 2 1。
程序代碼如下：
Private Sub Cycl(p() As Integer,ByVal k As Integer)
If k > n Then
???OutL p
???tot = tot + 1
Else
???For i = 0 To k - 1
t = p(1)
For j = 2 To k
p(j - 1) = p(j)
Next
p(k) = t
Cycl???p,k + 1
???Next
End If
End Sub


C++全排列之非遞歸算法:字典序法

題目：1~n的全排列

思想：（字典序法）初始化數組為1,2,3,...,n作為開端；設法從后續排列中找到大于前次結果但小于其他結果的序列；依此找出這樣的序列（后面序列肯定大于前面序列），則最后一個序列肯定是n,...,3,2,1
步驟：

• 假設情景：找“*243”該序列的下一個后續序列
• 從后往前找，找到這樣一個數，它后面的數更大，（即找到"*24*"，取2作為當前數，下標為i）
• 在“2”的后面，找到最接近2且比2大的數，這里找到“3”（下標為j）
• 調換a[i]和a[j]的值
• 對a[i+1]……a[n-1]進行轉置
• 此時數組a中的數就是所求后續序列
• 從1,2,3,...,n依此求出后續序列（即重新進行上面步驟），一直找到i=0且a[0]>a[1]則算法結束，全排列已全部給出。

三思：

• 怎么保證后面的序列比前面的大？首先開端是序列中最小的，i后面的部分是倒敘排列的，再對調（保證了大于前面序列）后，對i后面的進行逆置，保證了自身是后續排列中最小的，所以小于前面大于后面，依此遞增，直到n,...,3,2,1算法結束。
• 該算法要給一個開端，對于求“142”全排列這種情況，是不是還需要進行先排序得到“124”后再處理？
• 該算法對調操作頻繁，還有轉置操作，相比較于遞歸調用函數，時間更少了，但心里不是滋味。
• 處理"1223"這種情況又怎樣？遞歸方法不能處理，但這種方法可以處理。
• 對于字符排序"abc","abb"這兩種情況，貌似與數字排序"123","122"一樣，反正字符也可以比較大小，所以這兩種情況也可以得到解決。

其他：頭文件#include<algorithm>提供字典序法求后續序列的函數為next_permutation(_, _)。

代碼：

#include <iostream> using?namespace?std; const?int?MaxNum=9; int?iArr[MaxNum]; int?count; inline?void?printArr(int?n)//打印數組，n為元素的總個數 { int?i; for(i=0;i<n;i++)cout<<iArr[i]; cout<<endl; count++; } inline?void?Swap(int?i,int?j)//調換iArr[i]與iArr[j]的值 { int?temp=iArr[i]; iArr[i]=iArr[j]; iArr[j]=temp; } void?Transpose(int?k,int?m)//把數組下標為k~m的數轉置 { int?i,j; for(i=k,j=m;j>i;i++,j--)Swap(i,j); } int?FullArray2(const?int?n)//對1~n進行全排列 { if(1==n){cout<<"1"<<endl;count++;return?1;}//特殊情況n=1 int?i,j; while(1){ printArr(n); for(i=n-2;i>=0;i--){//要求n>=2 if(iArr[i]<iArr[i+1])break;//先求i if(0==i)return?1;//函數出口：當i=0且iArr[0]>iArr[1]時，函數結束 } for(j=n-1;j>i;j--){ if(iArr[i]<iArr[j])break;//后求j } Swap(i,j);//調換iArr[i]與iArr[j]的值 Transpose(i+1,n-1);//把i后面的數轉置 } } void?main() { int?i,n; while(1){ system("cls"); count=0;//測試新用例時,count重新置0 cout<<"請輸入n（最大為9）："; cin>>n; if(n>MaxNum || n<1){cout<<"Error: n的值在設定值范圍之外"<<endl;break;} for(i=0;i<n;i++)iArr[i]=i+1;//由于FullArray2上一次調用完，不會把調換的元素調整回來，故每次調用FullArray2前都要對數組進行重新初始化，即這條語句不能放在while循環外。 FullArray2(n); cout<<"1~"<<n<<"的全排列的個數："<<count<<endl; system("pause"); } }
來源:http://blog.sina.com.cn/s/blog_4cd4ffc401018x7r.html

總結

以上是生活随笔為你收集整理的全排列的生成算法:字典序法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。