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