有序全排列生成算法
作者：goal00001111（高粱）
寫本文的動力來自一個NOI題目：輸出n個數的第m種全排列。
輸入兩個自然數m,n 1<=n<=20，1<=m<=n!
輸出n個數的第m種全排列。
要解決這個問題，必須要生成有序的全排列。
生成n個數字的全排列是算法學習中的一個經典案例，也是信息學奧賽中的一個常考內容，值得我們去深入研究。生成全排列的算法很多，大概分類有直接模擬法，設置中介數法和數學分析法（這是我杜撰的一個名稱），其中直接模擬法又可以分為遞歸和非遞歸模擬。設置中介數后，更是可以分為字典序全排列生成法，遞增進位排列生成算法，遞減進位排列生成算法和循環左移排列生成算法等類別。此外還有鄰位對換法和鄰元素增值法等另類生成方法。利用這些算法生成的全排列，有些是有序全排列，有些卻是無序的，本文主要探討有序全排列。
在上面列舉的算法中，字典序全排列生成法和鄰元素增值法，以及我杜撰的數學分析法可以生成有序全排列，即可以輸出n個數的第m種全排列。其中字典序全排列生成法根據是否設置中介數又可以分為兩類，不用設置中介數的方法即直接模擬法。
我們首先來看最簡單的遞歸直接模擬法。這是普通遞歸方法的一個改進。普通的遞歸方法是利用將當前數組左界元素與其右側的元素交換位置來實現排列，這樣得到的全排列是無序的。所以我們不能直接調換位置，而是將左界右側的元素順序右移，不破壞原排列的順序，保證右側元素的遞增性。
為了回答本文開頭提出的問題，我們統一設置一個接口void
Permutation(long long n, long long m);其中n表示共n個自然數，m表示第m種全排列。
在子程序中我們先創建一個數組a[n]來存儲n個自然數，然后遞歸查找并輸出n個數的第m種全排列。下面是主要的代碼：（完整的代碼附在文章后面，下同）
/*
函數名稱：Permutation
函數功能：輸出n個數的第m種全排列
輸入變量：long long n：1，2，3，...，n共n個自然數（1<=n<=20）
long long m：第m種全排列（1<=m<=n!）
輸出變量：無
*/
void Permutation(long long n, long long m)// 遞歸直接模擬法
{
long long *a = new long
long[n];//用來存儲n個自然數
for (int i=0; i<n; i++)
{
a[i] = i + 1;
}
long long s = 0;//記錄當前是第幾個全排列
Try(a, 0, n-1, m, s);//遞歸查找并輸出n個數的第m種全排列
delete []a;
}
/*
函數名稱：Try
函數功能：遞歸查找并輸出n個數的第m種全排列
，找到第m種全排列返回true，否則返回false
輸入變量：long long a[]：用來存儲n個自然數，按照第m種全排列存儲
int left：數組的左界
int right：數組的右界
long long m：第m種全排列（1<=m<=n!）
long long & s：記錄當前是第幾個全排列
輸出變量：找到第m種全排列返回true，否則返回false
*/
bool Try(long long a[], int left, int right, long long m, long long
& s)
{
if (left == right)//已經到達數組的右界，直接輸出數組
{
s++;
if (s == m)//找到第m種全排列
{
cout << s
<< ": ";
for (int i=0;
i<=right; i++)
{
cout <<
a[i] << ' ';
}
cout <<
endl;
return true;
}
}
else
{ //將當前最左邊的元素與其后面的元素交換位置
//當i=left時，與自身交換，相當于不換，直接輸出
for (int i=left;
i<=right; i++)
{//這是與其他遞歸算法所不同的地方，其他算法是Swap(a[left],a[i]);
MoveRight(a, left,
i);
if (Try(a, left+1, right, m, s))//左界右移一位，遞歸尋找第m種全排列
{
return true;
}
MoveLeft(a, left,
i);//再換回來
}
}
return false;
}
在遞歸函數Try中，我們每次只分析left與right之間的元素，并不斷將left右移，當left==right時，一個全排列被生成。
在這里我們用void MoveRight(long long a[],
int left, int right)代替普通遞歸算法中的void Swap(long long a[], int left, int right)；函數功能是將left與right之間的元素按順序右移，而right位置的元素左移到left位置。這樣可以保證left+1與right之間的元素按增序排列。
我在這里先簡單的介紹子函數MoveRigh和MoveLeft的功能，而把重點放在對主要功能函數Permutation和Try的理解上。函數的完整代碼我放在了文章后面，有興趣的讀者也可以自己實現。以下的內容也采用這種方法。
遞歸直接模擬法算法簡單明了，當m較小的時候還是很實用的（與n的大小關系不大），我的測試結果是當n = 100，m=10000000時，用時為1秒；當n = 1000，m=10000000時，用時為2秒；當n = 10000，m=10000000時，用時為3秒。
比遞歸直接模擬法速度更快的是循環直接模擬法，用循環代替遞歸，可以大大的減小開銷，提高速度。循環直接模擬法又叫字典序生成算法，以下有關字典序生成算法的文字轉載自網友visame的專欄。
字典序生成算法：
設P是1～n的一個全排列:p = p1p2...pn = p1p2...pj-1pjpj+1......pk-1pkpk+1...pn
1）從排列的右端開始，找出第一個比右邊數字小的數字的序號j（j從左端開始計算），即j = max{i | pi <
pi+1}
2）在pj的右邊的數字中，找出所有比pj大的數中最小的數字pk，即 k = max{i | pi < pi+1}
（右邊的數從右至左是遞增的，因此k是所有大于pj的數字中序號最大者）
3）對換pj，pk
4）再將pj+1......pk-1pkpk+1...pn倒轉得到排列p' = p1p2...pj-1pjpn......pk+1pkpk-1...pj+1，
這就是排列p的下一個排列。
例如839647521是數字1～9的一個排列。從它生成下一個排列的步驟如下：
自右至左找出排列中第一個比右邊數字小的數字4；
在該數字后的數字中找出比4大的數中最小的一個5；
將5與4交換得到839657421；
將7421倒轉得到839651247；
所以839647521的下一個排列是839651247。
下面我們用c++代碼來實現字典序生成算法，函數接口與遞歸直接模擬法完全一樣。在子程序中我們先創建一個數組a[n]來存儲n個自然數，然后使用循環直接輸出n個數的第m種全排列。下面是主要的代碼：（完整的代碼附在文章后面，下同）
void Permutation(long long n, long long m)
{
long long *a = new long
long[n];//用來存儲n個自然數
for (int i=0; i<n; i++)
//存儲全排列的元素值
{
a[i] = i + 1;
}
cout << m <<
": "; //輸出n個數的第m種全排列
int left, right;
long long temp;
for (int i=1; i<m; i++)
{
left = n - 2; //設置需要改變的元素的左邊界，保證此時左邊界右邊的元素是一個遞減排列
while (left >= 0
&& a[left] > a[left+1])
left--;
right = n - 1;
while (a[right] <
a[left])//找到左邊界右邊數組中比a[left]大的最小的元素，這個就是要取代a[left]的元素
right--;
temp = a[left];
a[left] = a[right]; a[right] = temp; //交換a[right]和a[left]
left++; //左邊界增1，保證此時左右邊界之間的元素是一個遞減排列
right = n -1;
while (left <
right)//逆置左右邊界之間的元素，使其按增序排列
{
temp = a[left];
a[left] = a[right]; a[right] = temp;
left++;
right--;
}
}
for (int i=0; i<n; i++)
{
cout << a[i]
<< " ";
}
cout << endl;
delete []a;
}
與遞歸直接模擬法算法相比較，循環直接模擬法在m較大具有明顯優勢，我的測試結果是當n = 100，m=10000000時，遞歸直接模擬法用時為1秒，而循環直接模擬法用時為0秒；當n = 100，m=50000000時，遞歸直接模擬法用時為8秒，而循環直接模擬法用時為3秒。
接下來要講的第三種算法是需要設置中介數的字典序全排列生成法，這是我從組合數學的教材中獲得的一種方法。它通過生成初始排列的中介數和序數m的遞增進位制數，產生一個新的映射，再將映射還原，得到新的全排列。以下關于遞增進位制和字典全排列生成法的映射和還原方法轉載自speedfirst
的Blog。
遞增進位制和遞減進位制數：
所謂遞增進位制和遞減進位制數字是指數字的進制隨著數字位置的不同遞增或遞減。通常我們見到的都是固定進制數字，如2進制，10進制等。m位n進制數可以表示的數字是m*n個。而m位遞增或遞減進位制數則可以表示數字m!個。例如遞增進位制數4121，它的進制從右向左依次是2、3、4、5。即其最高位（就是數字4那位）最大值可能是4；第三高位最大可能是3；第二高位最大可能是2；最末位最大可能是1。如果將4121加上1的話，會使最末位得到0，同時進位；第二位的2與進位相加，也會得到0，同時進位；第三位的1與進位相加得到2，不再進位。最終得到結果是4200。遞減進位制的道理是一樣的，只不過進制從右向左依次是9、8、7、6……，正好與遞增進位制相反。
接下來要了解的是遞增進位制、遞減進位制數和其序號的關系。遞增、遞減進位制數可以被看作一個有序的數字集合。如果規定遞增進位制和遞減進位制數的0的序號是十進制0，遞增進位制數的 987654321和遞減進位制數的123456789對應十進制序號362880（即9!），則可以整理一套對應法則。其中，遞增進位制數（a1 a2 a3 a4 a5 a6 a7 a8 a9）為：
a1*9! + a2*8! + ….+ a8*2! + a9*1! = 序號
例如序號100的遞增進位制數就是4020，即4*4！+ 0*3！+ 2*2！+ 0*1！= 100。將一個序號轉換成其遞增進位制數首先需要找到一個比序號小的最大階乘數（即1、2、6、24、120、720……），對其進行整數除得到遞增進位制的第一位；將除法的余數反復應用這個方法（當然，之后選擇的余數是小一級的階乘數），直到余數為0。
遞減進位制數（a1 a2 a3 a4 a5 a6 a7 a8 a9）為：
(((((((((a1 * 1 + a2) * 2 + a3) * 3 + …… + a7) * 8 + a8) * 9 + a9 = 序號
例如序號100的遞減進位制數就是131，即（1*8 + 3）*9 + 1 = 100。將一個序號轉換成其遞減進位制數，需要對序號用9取余數，就可以得到遞減進位制的最末位（這點和遞增進位制先算出最高位相反）。用序號整除9的商作為新的序號重復此過程（當然，依次對8、7、6……取余求商），直到余數為0。
關于遞增進位制和遞減進位制需要注意的重點：一是其加減法的進位需要小心；二是序號和數字的轉換。除了100之外，常見的轉換有：999的遞增數是 121211，遞減數是1670；99的遞增數是4011，遞減數是130。
上面的一段文字是我從網友speedfirst的博客中轉載而來的，而關于已知序號求遞增進位制數和遞減進位制數，以及求字典序全排列生成算法的映射方法等功能函數，我已經用c++語言實現了，并附在本文的末尾，有興趣的讀者可以參考一下。
接下來我們看字典序全排列生成算法的映射和還原方法。
映射方法：將原排列數字從左到右（最末尾不用理會），依次查看數字右側比其小的數字有幾個，個數就是中介數的一位。例如，對于排列839647521。最高位8右側比8小的有7個數字，次高位3右側比3小的數字有2個，再次位的9的右側比9小的有6個數字，……，2的右側比2小的數有1個。得到遞增進制中介數 72642321。（此中介數加上100的遞增進位制數4020后得到新中介數72652011）。
還原方法：還原方法為映射方法的逆過程。你可以先寫出輔助數字1 2 3 4
5 6 7 8 9，以及9個空位用于填充新排列。然后從新中介數的最高位數起。例如新中介數最高位是x，你就可以從輔助數字的第一個沒有被使用的數字開始數起，數到x。第x+1個數字就應當是空位的第一個數字。我們將此數字標為“已用”，然后用其填充左起第一個空位。然后，再看新中介數的次高位y，從輔助數字的第一個未用數字數起，數到1。第y+1個數字就是下一個空位的數字。我們將此數字標為“已用”，然后用其填充左起第二個空位。依此類推，直到最后一個中介數中的數字被數完為止。例如對于新中介數72652011，我們給出其輔助數字和空位的每一步的情況。其中紅色的數字代表“正在標記為已用”，“已用”的數字不會 再被算在之后的計數當中。當新中介數中所有的數字都被數完了，輔助數字中剩下的唯一數字將被填入最后的空位中。最終得到新排列839741562。
|
新中介數當前位
|
輔助數字
|
新排列數
|
|
初始
|
1 2 3 4 5 6 7 8 9
|
|
|
7
|
1 2 3 4 5 6 7 8 9
|
8
|
|
2
|
1 2 3 4 5 6 7 8 9
|
8 3
|
|
6
|
1 2 3 4 5 6 7 8 9
|
8 3 9
|
|
5
|
1 2 3 4 5 6 7 8 9
|
8 3 9 7
|
|
2
|
1 2 3 4 5 6 7 8 9
|
8 3 9 7 4
|
|
0
|
1 2 3 4
5 6 7 8 9
|
8 3 9 7 4 1
|
|
1
|
1 2 3 4 5 6 7 8 9
|
8 3 9 7 4 1 5
|
|
1
|
1 2 3 4
5 6 7 8 9
|
8 3 9 7 4 1 5 6
|
|
最后補位
|
|
8 3 9 7 4 1 5 6 2
|
要想得到n個數字的第m個全排列，我們只需要設初始全排列為123456789，序數為（m-1），通過映射和還原后就可以得到第m個全排列了。主要功能函數的c++代碼如下：
void Permutation(long long n, long long m)
{
int *a = new int[n];//用來存儲n個自然數，也可以看成是初始全排列1234...n
for (int i=0; i<n; i++)
{
a[i] = i + 1;
}
long long s = 1;
long long *p = new long
long[n];//用來存儲各個全排列的值，p[i]=i!
for (int i=0; i<n; i++)
{
s *= a[i];
p[i] = s;
}
cout << m <<
": "; //輸出n個數的第m種全排列
int *diZ = new int[n-1];
//用來存儲序號m的遞增進位制數，設所有元素的初值為0
for (int i=0; i<n-1;
i++)
{
diZ[i] = 0;
}
DiZeng(diZ, p, n-1,
m-1);//獲取序號（m-1）的遞增進位制數
int *zhongJie = new
int[n-1];
for (int i=0; i<n-1;
i++)//設初始全排列的中介數為0
zhongJie[i] = 0;
YingShe(zhongJie, diZ,
n);//將原中介數加上序號（m-1）的遞增進制數得到新的映射
//將映射還原，得到新的全排列b
int *b = new int[n];//用來存儲新的全排列
for (int i=0; i<n-1;
i++) //獲取前n-1個數字
{
s = 0;
int j = 0;
while (s <
zhongJie[i])
{
if (a[j] != -1)
s++;
j++;
}
while (a[j] == -1)
j++;
b[i] = a[j];
a[j] = -1; //用-1表示該位置已經被填充
}
for (int i=0; i<n;
i++)//填充最后一個數字
{
if (a[i] != -1)
{
b[n-1] = a[i];
break;
}
}
for (int i=0; i<n; i++)
{
cout << b[i]
<< ' ';
}
cout << endl;
delete []a;
delete []b;
delete []p;
delete []diZ;
delete []zhongJie;
}
設置了中介數的字典序全排列生成算法，與遞歸直接模擬法和循環直接模擬法的最大不同是，不需要模擬有序全排列的生成過程，也就不需要逐一地生成各個全排列，只要知道初始全排列，就能根據序號（m-1），直接得到第m個全排列，因此速度非常快。它的缺點是在生成序號（m-1）的遞增進進制數時，需要事先創建一個用來存儲n的階乘數n! 的數組p[]，所以n的值不能太大，否則就會溢出，根據我的測試結果，當1<=n<=20時不會溢出，當21<=n時會溢出。
測試比較：當n = 20，m=10000000時，遞歸直接模擬法用時為1秒，循環直接模擬法用時為0秒，而字典序全排列生成算法用時為0秒；當n = 20，m=50000000時，遞歸直接模擬法用時為8秒，循環直接模擬法用時為3秒，而字典序全排列生成算法用時為0秒；
當n = 20，m=500000000時，遞歸直接模擬法用時超過80秒，循環直接模擬法用時為50秒，而字典序全排列生成算法用時為0秒；實際上，對于long long范圍內的任意自然數，字典序全排列生成算法用時都是0秒。
接下來介紹一個我原創的東西，我稱之為數學分析法，因為它的發現是對各個全排列的數學規律進行分析后得到的。這個算法是我在做本文開頭的題目時自己想出來的，后來去網上搜索時也沒有發現類似算法。其實我的算法和字典序全排列生成算法思路有點相同，只不過我沒有設置中介數而已。后來聽說有一個叫什么康托展開的東西，它是已知某個有序全排列，可以求出它的序號，跟本文談論的話題剛好相反，但是使用逆向思維的方法，可以從中得到啟發——關于康托展開的實現代碼我也在文章末尾給出了。
我的算法也許和康托展開有一定關系——我不知道，因為我也是事后才知道有康托展開一說的——大家可以去尋找一下兩者的聯系。
算法思路是利用n個數字的全排列總量是n!個的原理，如果m小于i！，則前n-i個元素無需移動位置，這樣相當于求i個數字的第m個全排列，范圍縮小了。再使用迭代的方法，不斷的減小m的值，縮小全排列的范圍，直到能夠直接寫出全排列。這一點和求遞增進位制數的算法很相似，
具體的操作是用一個數組順序存儲n個數字，數組初始化為順序排列的n個數字，即a[n]={1,2,...,n-1}
；再用一個數組順序存儲n個數字的全排列數量,即n!，得到p[n]={1,2,6,...,n!} 。
選擇點一：如果m=1，則直接輸出數組a[n]；
選擇點二：如果m=2，則調換a[n-1]與a[n-2]，再輸出數組a[n]；
選擇點三：若m>2，查找p[r-1] <
m <= p[r]，設左界left =
n-r+1；
選擇點四：若m = p[r]，從a[0]~a[left-1]的元素原樣輸出，從left開始到最后的元素逆序輸出；
選擇點五：若m < p[r]， 設s = m/p[r-1]，y = m%p[r-1]；
選擇點六：若y = 0，則從a[0]~a[left-1]的元素原樣輸出，a[left]=a[left+s-1]；left之后的元素逆序輸出；
選擇點七：若y != 0，則從a[0]~a[left-1]的元素原樣輸出，a[left]=a[left+s]，m = y；
轉化為求left之后的元素的第m（此時m也已經變小）個全排列。
C++代碼實現主要功能函數如下：
void
Permutation(long long n, long long m)
{
long long *a = new long long[n];//用來存儲n個自然數
for (int i=0; i<n; i++)
{
a[i] = i + 1;
}
long long s = 1;
long long *p = new long long[n];//用來存儲各個全排列的值，p[i]=i!
for (int i=0; i<n; i++)
{
s *= a[i];
p[i] = s;
}
cout << m << ": "; //輸出n個數的第m種全排列
while (m > 1)//通過判斷m的值排列數組a的元素
{
//若m=1，什么也不做，直接輸出數組
if (m == 2) //若只要求輸出第2個排列，直接交換數組最后兩個元素
{
long long temp = a[n-1];
a[n-1] = a[n-2];
a[n-2] = temp;
break; //跳出循環
}
else if (m > 2)
{
int pos = Compare(p, n, m);//查找pos，使得p[pos-1] < m <= p[pos]
int left = n - 1 - pos;//由于m <= p[pos]，所以前n-1-pos個元素不必移動，故讓數組的左界移至n-1-pos位
if (p[pos] == m)//如果p[pos] == m，直接逆置以left為左界的數組
{
Reverse(a, left, n-1);//逆置數組[left, n-1)]區間的元素
break; //跳出循環
}
else
{
int r = m / p[pos-1] + left;//計算將要置放在left位的元素位置
m %= p[pos-1]; //改變m的值----這是本算法的關鍵！
if (m == 0)//如果m是p[pos-1]的倍數，將第r-1位元素移動到left位
{
Move(a, left, r-1);
Reverse(a, left+1, n-1); //逆置數組[left+1, n-1)]區間的元素
}
else//否則將第r位元素移動到left位，并根據新的m值計算全排列 {
Move(a, left, r);
}
}
}
}
for (int i=0; i<n; i++)
{
cout << a[i] << "
";
}
cout << endl;
delete []a;
delete []p;
}
這里同樣需要事先創建一個用來存儲n的階乘數n! 的數組p[]，所以n的值不能太大。使用了三個子函數int Compare(long long p[], int n, long long m)，void Reverse(long long a[], int
left, int right)和void
Move(long long a[], int left, int pos)，實現的功能分別為：
Compare用來尋找使得p[pos-1] < m <= p[pos]的數組下標pos，確保m<=p[n-1]，返回滿足條件的數組下標pos；Reverse用來逆置數組的左界left和右界right直接的元素；Move負責將pos位的元素向左移動到left位，而left~（pos-1）位的元素則依次右移一位，功能其實和遞歸直接模擬法中用到的MoveRight一模一樣。和前面的子函數一樣，完整代碼放在了文章末尾的附錄中。
我的數學分析法的速度幾乎和字典序全排列生成算法一樣快，當n = 20，m=500000000時，用時為0秒。由于不需要構造中介數，所以我認為數學分析法比字典序全排列生成算法容易理解——只需要一點點排列組合的知識和一點點邏輯推理能力，呵呵！
最后再給大家介紹一種比較另類的方法：鄰元素增值法（n進制法）。算法思路如下：
1）從原始排列p = p1p2......pn開始，第n位加n-1，如果該位的值超過n，則將它除以n，用余數取代該位，并進位（將第n-1位加1），執行2）；若沒有進位則產生一個新的排列，跳過2），3），直接執行4）；
2）若第n位產生了進位，將第n-1位加1。若第n-1位的值超過n，則將它除以n，用余數取代該位，并進位；
3）按同樣方法處理n-2位，n-1位，......，直至不再發生進位為止，處理完一個排列，產生一個新的排列；
4）若新全排列中有相同元素，則表示該全排列錯誤，不能記錄到全排列總數中；
5）當第一個元素的值大于n時，所有全排列都已經產生，程序結束。
以3個數1，2，3的全排列為例：
原始排列是1 2 3，從它開始，第3個元素是3，3 + 2 = 5 > 3，有進位，5 mod 3 = 2；第2個元素是2，2+1 = 3，沒有進位，所以新排列是1 3 2。
由于此時第一個元素的值1不大于3，繼續對排列1 3 2進行鄰元素增值操作：第3個元素是2，2 + 2 = 4 > 3，有進位，4 mod 3 =1；第2個元素是3，3+1 = 4 > 3，有進位，4 mod 3 =1；第1個元素是1，1+1 = 2，沒有進位，所以新排列是2 1 1。
繼續對排列2 1 1進行鄰元素增值操作，得到新排列2 1 3。
依此類推，直到第一個元素的值大于3，我們可以得到所有的全排列（包括錯誤的排列）。
順序產生的排列是：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
有的排列中存在重復元素（如2 1 1和2 2 2等），丟棄，余下的就是所有正確的全排列，而且我們可以發現，這些全排列是有序的。
C++代碼實現如下：
void Permutation(long long n, long long m)
{
long long *a = new long
long[n];//用來存儲n個自然數
for (int i=0; i<n; i++)
//存儲全排列的元素值
{
a[i] = i + 1;
}
cout << m <<
" : ";
long long s = 1;
int pos;
while (s < m)
{
pos = n - 1; //最后一位加n-1
a[pos] = (a[pos] +
pos);
while (a[pos] >
n)//若有進位，前一元素加1，直到沒有進位為止
{
a[pos--] -= n;//大于n則取余數，實際上a[pos]一定比2*n小
a[pos] += 1; //前一元素加1
}
if (a[0] > n)//當第一個元素的值>n則結束
break;
if (IsRight(a, n))//若數組a中不存在重復元素，說明得到了一個正確的全排列
{
s++;
}
}
for (int i=0; i<n; i++)
cout << a[i];
cout << endl;
delete []a;
}
其中用到了一個子函數bool IsRight(long long
a[], int n)，作用是判斷當前全排列是否正確，即數組a中是否存在重復元素，若存在重復元素則返回false，否則返回true。
此種算法實現起來非常簡單，是上述所有算法中代碼最短的一個，但是由于每得到一個新的全排列，都要遍歷數組a[]判斷是否有重復元素，增大了計算量，大大減緩了速度，所以成了速度最慢的一個。我們拿它和模擬法算法進行比較。
當n = 10，m=10000時，三種算法用時均為0秒；當n = 10，m=100000時，遞歸直接模擬法用時為0秒，循環直接模擬法用時為0秒，而鄰元素增值法用時為5秒；當n = 10，m=200000時，遞歸直接模擬法用時為0秒，循環直接模擬法用時為0秒，而鄰元素增值法用時為10秒。
到這里，我就把我目前所知的五種有序全排列的生成算法都向大家做了介紹，它們或直截了當，或曲徑通幽，或代碼簡短，或速度迅捷。所謂“蘿卜白菜，各有所愛”，希望閱讀了全文的讀者們都能有所收獲。
另外，如果大家不覺得讀我的文章是浪費時間，并且意猶未盡的話，我打算將其他的幾種非有序排列算法在下一篇文章中向大家介紹，這些算法雖然不能生成有序全排列，但是速度非常快，非常值得一看。
參考文獻：
1.《組合數學——排列數生成算法詳解》speedfirst 的Blog
http://www.newsmth.net/pc/pcdoc.php?userid=speedfirst&pid=0&tag=0&order=&tid=18452
2.《全排列的生成算法》 visame的專欄
http://blog.csdn.net/visame/archive/2008/05/18/2455396.aspx
附錄：
《康托展開》：http://blog.csdn.net/goal00001111/archive/2008/11/18/3326662.aspx
《遞增進位制和遞減進位制數》：
http://blog.csdn.net/goal00001111/archive/2008/11/18/3326765.aspx
《有序全排列生成算法集錦》
http://blog.csdn.net/goal00001111/archive/2008/11/18/3326642.aspx