生成下一個(gè)排列的字典序法
字典序法中，對(duì)于數(shù)字1、2、3......n的排列，不同排列的先后關(guān)系是從左到右逐個(gè)比較對(duì)應(yīng)的數(shù)字的先后來(lái)決定的。例如對(duì)于5個(gè)數(shù)字的排列12354和12345，排列12345在前，排列12354在后。按照這樣的規(guī)定，5個(gè)數(shù)字的所有的排列中最前面的是12345，最后面的是54321。
字典序算法如下：
設(shè)P是1～n的一個(gè)全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1）從排列的右端開(kāi)始，找出第一個(gè)比右邊數(shù)字小的數(shù)字的序號(hào)j（j從左端開(kāi)始計(jì)算），即 j=max{i|pi<pi+1}
2）在pj的右邊的數(shù)字中，找出所有比pj大的數(shù)中最小的數(shù)字pk，即 k=max{i|pi>pj}（右邊的數(shù)從右至左是遞增的，因此k是所有大于pj的數(shù)字中序號(hào)最大者）
3）對(duì)換pj，pk
4）再將pj+1......pk-1pjpk+1pn反轉(zhuǎn)，這就是排列p的下一個(gè)下一個(gè)排列。
例如839647521是數(shù)字1～9的一個(gè)排列。從它生成下一個(gè)排列的步驟如下：
自右至左找出排列中第一個(gè)比右邊數(shù)字小的數(shù)字4 839647521
在該數(shù)字后的數(shù)字中找出比4大的數(shù)中最小的一個(gè)5 839647521
將5與4交換 839657421
將7421倒轉(zhuǎn) 839651247
所以839647521的下一個(gè)排列是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 '從排列右端開(kāi)始
If p(i) <= p(j) Then Exit For '找出遞減子序列
Next
Swap p(i), p(j) '將遞減子序列前的數(shù)字與序列中比它大的第一個(gè)數(shù)交換
For j = n To 1 Step -1 '將這部分排列倒轉(zhuǎn)
i = i + 1
If i >= j Then Exit For
Swap p(i), p(j)
Next
OutL p '輸出一個(gè)排列
i = n
End If
i = i - 1
Loop
End Sub
Swap p(i), p(j)是交換兩個(gè)元素的子過(guò)程，OutL p是輸出排列的子過(guò)程。