非有序全排列生成算法
作者：goal00001111（高粱）
我曾經(jīng)寫過一篇《有序全排列生成算法》，介紹了五種生成有序全排列的方法，在該文的末尾，我計劃再寫一篇姊妹篇《非有序全排列生成算法》，由于各種原因，一直遲遲未動筆，前幾天學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)“棧”的時候，碰到一個有趣的問題“列車出棧序列”，其中有一種解法需要用到非有序全排列，所以決定先寫好本文，再總結(jié)該問題。
生成非有序全排列的算法很多，有普通遞歸算法，循環(huán)移位法，鄰位對換法，需要中介數(shù)的遞增進(jìn)位排列生成算法，遞減進(jìn)位排列生成算法和循環(huán)左移排列生成算法等。
我們先看最簡單的普通遞歸算法，它的原理是：
如果用P表示n個元素的排列，而Pi表示不包含元素i的排列，(i)Pi表示在排列Pi前加上前綴i的排列，那么，n個元素的排列可遞歸定義為：
如果n=1，則排列P只有一個元素i
如果n>1，則排列P由排列(i)Pi構(gòu)成（i=1、2、....、n-1）。
根據(jù)定義，容易看出如果已經(jīng)生成了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。
主要代碼如下：
/*
函數(shù)名稱：Permutation
函數(shù)功能：普通遞歸算法：輸出n個數(shù)的所有全排列
輸入變量：int n：1，2，3，...，n共n個自然數(shù)
輸出變量：無
*/
void Permutation(int n)
{
int *a = new
int[n];//用來存儲n個自然數(shù)
for (int
i=0; i<n; i++) //存儲全排列的元素值
a[i] = i
+ 1;
Recursion(a,
n, n-1); //調(diào)用遞歸函數(shù)
delete []a;
}
/*
函數(shù)名稱：Recursion
函數(shù)功能：遞歸輸出n個數(shù)的所有全排列
輸入變量：int a[]：存儲了1，2，3，...，n共n個自然數(shù)的數(shù)組
int n：數(shù)組a[]的長度
int k：正在處理的k個元素所組成的排列
輸出變量：無
*/
void Recursion(int a[], int n, int k)
{
if (k == 0)
//排列只有一個元素a[k]，直接輸出
Print(a,
n);
else
{
int
temp;
for (int
i=0; i<=k; i++) //窮舉，依次讓第k個元素與前面的元素交換
{
temp
= a[i];
a[i]
= a[k];
a[k]
= temp;
Recursion(a, n, k-1); //遞歸生成k-1個元素的全排列
temp
= a[i]; //再換回來
a[i]
= a[k];
a[k]
= temp;
}
}
}
void Print(int a[], int n)
{
for (int
i=0; i<n; i++)
cout
<< a[i];
cout
<< endl;
}
循環(huán)移位法是一種很容易理解的非有序全排列算法，它的原理是：如果已經(jīng)生成了k-1個元素的排列，則在每個排列后添加元素k使之成為k個元素的排列，然后將每個排列循環(huán)左移（右移），每移動一次就產(chǎn)生一個新的排列。
例如2個元素的排列是1 2和2 1。在1 2 后加上3成為新排列1 2 3，將它循環(huán)左移可再生成新排列2 3 1、3 1 2，
同樣2 1 可生成新排列2 1
3、1 3 2和3 2 1。
代碼也和簡單，使用了遞歸窮舉思想，我生成了一個循環(huán)左移的算法，有興趣的讀者可以自己生成一個循環(huán)右移的算法。
/*
函數(shù)名稱：Permutation
函數(shù)功能：全排列循環(huán)移位法：輸出n個數(shù)的所有全排列
輸入變量：int n：1，2，3，...，n共n個自然數(shù)
輸出變量：無
*/
void Permutation(int n)
{
unsigned int
*a = new unsigned int[n];//用來存儲n個自然數(shù)
for (int
i=0; i<n; i++) //存儲全排列的元素值，并計算全排列的數(shù)量
{
a[i] = i + 1;
}
Recursion(a,
n, 1);
delete []a;
}
/*
函數(shù)名稱：Recursion
函數(shù)功能：循環(huán)左移遞歸輸出n個數(shù)的所有全排列
輸入變量：int a[]：存儲了1，2，3，...，n共n個自然數(shù)的數(shù)組
int n：數(shù)組a[]的長度
int k：正在處理的k個元素所組成的排列
輸出變量：無
*/
void Recursion(unsigned int a[], int n, int k)
{
if (k >
n)
Print(a,
n);
else
{
int
temp;
for (int
i=0; i<k; i++)//循環(huán)左移
{
temp
= a[0];
for
(int j=1; j<k; j++)
a[j-1] = a[j];
a[k-1] = temp;
Recursion(a, n, k+1);
}
}
}
一個能夠快速生成全排列的算法叫做鄰位對換法，它之所以較快，是因為鄰位對換法中下一個排列總是上一個排列某相鄰兩位對換得到的，只需一步，就可以得到一個新的全排列，而且絕不重復(fù)，但是由于每將n從一端移動到另一端后，就需要遍歷排列2次，來尋找最大的可移數(shù)m，所以速度得到了限制。它的原理是：
[n]的全排列可由[n-1]的全排列生成：
給定[n-1]的一個排列п,將n 由最右端依次插入排列п ，即得到n個[n]的排列：
p1 p2…pn-1n
p1 p2…npn-1
np1 p2…pn-1
對上述過程，一般地，對i，將前一步所得的每一排列重復(fù)i次，然后將i由第一排的最后往前移，至最前列，正好走了i次,下一個接著將i放在下一排列的最前面，然后依次往后移，一直下去即得i元排列。
考慮{1,2…n}的一個排列，其上每一個整數(shù)都給了一個方向，如果它的箭頭所指的方向的鄰點小于它本身，我們稱整數(shù)k是可移的。
顯然1永遠(yuǎn)不可移，n除了以下兩種情形外，它都是可移的:
(1) n是第一個數(shù)，且其方向指向左側(cè)
(2) n是最后一個數(shù)，且其方向指向右側(cè)
于是，我們可按如下算法產(chǎn)生所有排列：
1，開始時：存在排列123…n，除1外，所有元素均可移，即方向都指向左側(cè)。
2，當(dāng)最大元素n可移動時，將其從一端依次移動到另一端，即可得到n-1個全排列；當(dāng)n移動到某一端后，不能再移動，此時尋找最大的可移數(shù)m，將m與其箭頭所指的鄰數(shù)互換位置，這樣就又得到一個新的全排列；將所得新排列中所有比m大的數(shù)p的方向調(diào)整，即改為相反方向，這樣使得n又成了可移數(shù)。
3，重復(fù)第2步直到所有的元素都不能移動為止。
以4個元素的排列為例，首先生成全排列1 2 3 4；
找到最大的可移數(shù)4，將4與其箭頭所指的鄰數(shù)互換位置，可以生成3個新排列：
1 2 4 3 1 4 2
3 4 1 2 3
因為沒有比4更大的數(shù)p，所以無需調(diào)整p的方向。最大數(shù)4到了最左邊后，由于其方向指向左側(cè)，所以4不能再移動。
接下來尋找最大的可移數(shù)3，將3與其箭頭所指的鄰數(shù)2互換位置，可以得到新排列：4 1 3 2；
然后將所得排列中比3大的數(shù)4的方向調(diào)整，使得4可以移動，重新成為最大的可移數(shù)，將4與其箭頭所指的鄰數(shù)互換位置，可以生成3個新排列：
1 4 3 2 1 3 4
2 1 3 2 4
此時最大數(shù)4到了最右邊，又因為其方向指向右側(cè)，所以4不能再移動；于是我們尋找最大的可移數(shù)3，將3與其箭頭所指的鄰數(shù)1互換位置，可以得到新排列：3 1 2 4；
然后將所得排列中比3大的數(shù)4的方向調(diào)整，使得4可以移動，重新成為最大的可移數(shù)，將4與其箭頭所指的鄰數(shù)互換位置，可以生成3個新排列：
3 1 4 2 3 4 1
2 4 3 1 2
如此循環(huán)，直到所有的數(shù)都不能移動，即可求出全部排列。最后得到的一個全排列為：2
1 3 4，此時2指向左側(cè)，1，3，4均指向右側(cè)。
根據(jù)上述算法分析，使用一個輔助數(shù)組來存儲各個元素的指向，我們可以得到代碼如下：
/*
函數(shù)名稱：Permutation
函數(shù)功能：排列鄰位對換法：輸出n個數(shù)的所有全排列
輸入變量：int n：1，2，3，...，n共n個自然數(shù)
輸出變量：無
*/
void Permutation(int n)
{
int *a = new int[n]; //用來存儲n個自然數(shù)
bool *p =
new bool[n]; //用來存儲n個元素的指向：向左為false，向右為true
for (int
i=0; i<n; i++) //存儲全排列的元素值，并計算全排列的數(shù)量
{
a[i] = i
+ 1;
p[i] =
false; //開始均指向左側(cè)
}
do
{
Print(a,
n); //輸出第一個全排列
if (n ==
a[n-1])//若n在最右側(cè)，將其逐次與左側(cè)的元素交換，得到n - 1個新的排列
{
for
(int i=n-1; i>0; i--)
{
int temp = a[i]; a[i] = a[i-1];
a[i-1] = temp;
bool flag = p[i]; p[i] = p[i-1]; p[i-1] = flag;
Print(a, n);
}
}
else //若n在最左側(cè)，將其逐次與右側(cè)的元素交換，得到n - 1個新的排列
{
for
(int i=1; i<n; i++)
{
int temp = a[i]; a[i] = a[i-1]; a[i-1] = temp;
bool flag = p[i]; p[i] = p[i-1]; p[i-1] = flag;
Print(a, n);
}
}
} while (Move(a,
p, n));
delete []a;
delete []p;
}
/*
函數(shù)名稱：Move
函數(shù)功能：尋找最大可移數(shù)，可移數(shù)m，將m與其箭頭所指的鄰數(shù)互換位置，
并將所得新排列中所有比m大的數(shù)p的方向調(diào)整
輸入變量：int a[]：存儲了1，2，3，...，n共n個自然數(shù)的數(shù)組
bool
p[]：存儲了n個元素的指向的數(shù)組：向左為false，向右為true
int n：數(shù)組a[]的長度
輸出變量：排列中存在最大可移數(shù)，則做了相關(guān)操作后返回真，否則直接返回假
*/
bool Move(int a[], bool p[], int n)
{
int max = 1;
int pos =
-1;
for (int
i=0; i<n; i++)
{
if (a[i]
< max)
continue;
if
((p[i] && i < n-1 && a[i] > a[i+1]) || //指向右側(cè)
(!p[i] && i > 0 &&
a[i] > a[i-1])) //指向左側(cè)
{
max
= a[i];
pos
= i;
}
}
if (pos ==
-1) //都不能移動
return
false;
//與其箭頭所指的鄰數(shù)互換位置
if (p[pos])
//指向右側(cè)
{
int temp = a[pos]; a[pos] = a[pos+1]; a[pos+1] =
temp;
bool
flag = p[pos]; p[pos] = p[pos+1]; p[pos+1] = flag;
}
else //指向左側(cè)
{
int temp = a[pos]; a[pos] = a[pos-1]; a[pos-1] =
temp;
bool
flag = p[pos]; p[pos] = p[pos-1]; p[pos-1] = flag;
}
//將所得排列中所有比max大的數(shù)p的方向調(diào)整
for (int
i=0; i<n; i++)
{
if (a[i]
> max)
p[i]
= !p[i];
}
return true;
}
遞增進(jìn)位排列生成算法是需要設(shè)置中介數(shù)的一種算法，它的映射和還原方法如下：
映射方法：將原排列按照從9到2的順序，依次查看其右側(cè)比其小的數(shù)字有幾個，個數(shù)就是中介數(shù)的一位。例如對于原排列839647521。9的右側(cè)比9小的數(shù)字有6個，8的右側(cè)比8小的數(shù)字有7個，7的右側(cè)比7小的數(shù)字有3個，……2的右側(cè)比2小的數(shù)字有1個。最后得到遞增進(jìn)制中介數(shù)67342221。（此中介數(shù)加上100的遞增進(jìn)制數(shù)4020得到新的中介數(shù)67351311）
還原方法：我們設(shè)新中介數(shù)的位置號從左向右依次是9、8、7、6、5、4、3、2。在還原前，畫9個空格。對于每一個在位置x的中介數(shù)y，從空格的右側(cè)向左數(shù)y個未被占用的空格。在第y+1個未占用的空格中填上數(shù)字x。重復(fù)這個過程直到中介數(shù)中所有的位都被數(shù)完。最后在余下的最后一個空格里填上1，完成新排列的生成。以新中介數(shù)67351311為例，我給出了詳細(xì)的恢復(fù)步驟。其中紅色數(shù)字代表新填上的數(shù)字。最后得到新排列869427351。
|
新中介數(shù)當(dāng)前位
|
新排列數(shù)
|
備注
|
|
初始
|
|
在還原前，畫9個空格
|
|
6
|
9
|
從右向左數(shù)6個空格，第7個空格里填“9”
|
|
7
|
8 9
|
從右向左數(shù)7個空格，第8個空格里填“8”
|
|
3
|
8 9 7
|
從右向左數(shù)3個空格，第4個空格里填“7”
|
|
5
|
8 6 9 7 9
|
從右向左數(shù)5個空格，第6個空格里填“6”
|
|
1
|
8 6 9 7 5 9
|
從右向左數(shù)1個空格，第2個空格里填“5”
|
|
3
|
8 6 9 4 7 5 7
|
從右向左數(shù)3個空格，第4個空格里填“4”
|
|
1
|
8 6 9 4 7 3 5 7
|
從右向左數(shù)1個空格，第2個空格里填“3”
|
|
1
|
8 6 9 4 2 7 3 5 7
|
從右向左數(shù)1個空格，第2個空格里填“2”
|
|
最后補位
|
8 6 9 4 2 7 3 5 1
|
余下的空格填“1”
|
我們設(shè)原中介數(shù)為0，然后讓中介數(shù)加上遞增序號1，根據(jù)上文將的方法得到新的中介數(shù)，最后還原新中介數(shù)，得到一個全排列。重復(fù)上述過程就可以得到所有所有的全排列。
主要代碼如下：
/*
函數(shù)名稱：Permutation
函數(shù)功能：遞增進(jìn)位排列生成算法：輸出n個數(shù)的所有全排列
輸入變量：int n：1，2，3，...，n共n個自然數(shù)
輸出變量：無
*/
void Permutation(unsigned int n)
{
unsigned int
*p = new unsigned int[n];//用來存儲各個全排列的值，p[i]=i!
p[0] = 1;
for (int
i=1; i<n; i++)
{
p[i] =
(i + 1) * p[i-1]; //cout << p[i] << " ";
}
int *b = new
int[n]; //用來存儲新的全排列
int *yShe =
new int[n-1]; //將原中介數(shù)加上序號i的遞增進(jìn)位制數(shù)得到新的映射
int *diZ =
new int[n-1]; //用來存儲序號i的遞增進(jìn)位制數(shù)，設(shè)所有元素的初值為0
for (int
i=0; i<n-1; i++)
{
diZ[i] =
yShe[i] = 0;
}
diZ[n-2] =
1; //存儲序號1，表示每次遞增1
for (int
c=0; c<p[n-1]; c++)
{
DiZYingShe(yShe, diZ, n); //每次遞增1后得到得到新的映射
for (int
i=0; i<n; i++) //新的全排列空格初始化
b[i]
= 0;
int num
= n;
for (int
j=0; j<n-1; j++) //獲取前n-1個數(shù)字
{
int
s = 0;
int
k = n - 1;
while (s < yShe[j])
{
if (b[k] == 0) //該處未填數(shù)字
s++;
k--;
}
while (b[k] != 0) //跳過已填數(shù)字
k--;
b[k]
= num--;
}
for (int
i=0; i<n; i++)//填充最后一個數(shù)字1
{
if
(b[i] == 0)
{
b[i] = 1;
break;
}
}
Print(b,
n);
}
delete []b;
delete []p;
delete
[]diZ;
delete
[]yShe;
}
/*
函數(shù)名稱：DiZYingShe
函數(shù)功能：遞增進(jìn)位排列生成算法的加法運算：yShe[] += dZJ[]
輸入變量：int yShe[]：原遞增進(jìn)制中介數(shù)；
int
diZ[]：遞增進(jìn)制數(shù)加數(shù)
int
len：最大自然數(shù)n的值
輸出變量：int yShe[]：新的增進(jìn)制中介數(shù)
*/
void DiZYingShe(int yShe[], int diZ[], int n)
{
int pos = n
- 2;
int r = 0;
while (pos
>= 0)
{
yShe[pos] += diZ[pos] + r;
if
(yShe[pos] >= n - pos)
{
yShe[pos] -= n - pos;
r =
1;
}
else
r =
0;
pos--;
}
}
遞減進(jìn)位制排列生成算法和遞增進(jìn)位制排列生成算法的原理很相似，都需要一個先映射一個中介數(shù)，我們設(shè)原中介數(shù)為0，讓中介數(shù)加上遞增序號1后再還原中介數(shù)，就得到一個全排列。
遞減進(jìn)位制和遞增進(jìn)位制的映射方法，以及還原方法都剛好相反。
映射方法：遞減進(jìn)位制的映射方法剛好和遞增進(jìn)位制相反，即按照從9到2的順序，依次查看其右側(cè)比其小數(shù)字的個數(shù)。但是，生成中介數(shù)的順序不再是從左向右，而是從右向左。生成的遞減進(jìn)制中介數(shù)剛好是遞增進(jìn)位排列生成算法得到中介數(shù)的鏡像。例如839647521的遞減進(jìn)制中介數(shù)就是12224376。（此中介數(shù)加上 100的遞減進(jìn)制數(shù)131后得到新中介數(shù)12224527）
還原方法：遞減進(jìn)位制中介數(shù)的還原方法也剛好和遞增進(jìn)位制中介數(shù)相反。遞增進(jìn)位制還原方法是按照從中介數(shù)最高位（左側(cè)）到最低位（右側(cè)）的順序來填數(shù)。而遞減僅位置還原方法則從中介數(shù)的最低位向最高位進(jìn)行依次計數(shù)填空。例如對于新中介數(shù)12224527，我給出了詳細(xì)的還原步驟。紅色代表當(dāng)前正在填充的空格。最終得到新排列
397645821。
|
新中介數(shù)當(dāng)前位
|
新排列數(shù)
|
備注
|
|
初始
|
|
在還原前，畫9個空格
|
|
7
|
9
|
從右向左數(shù)7個空格，第8個空格里填“9”
|
|
2
|
9 8
|
從右向左數(shù)2個空格，第3個空格里填“8”
|
|
5
|
9 7 8
|
從右向左數(shù)5個空格，第6個空格里填“7”
|
|
4
|
9 7 6 8 9
|
從右向左數(shù)4個空格，第5個空格里填“6”
|
|
2
|
9 7 6 5 8 9
|
從右向左數(shù)2個空格，第3個空格里填“5”
|
|
2
|
9 7 6 4 5 8 7
|
從右向左數(shù)2個空格，第3個空格里填“4”
|
|
2
|
3 9 7 6 4 5 8 7
|
從右向左數(shù)2個空格，第3個空格里填“3”
|
|
1
|
3 9 7 6 4 5 8 2 7
|
從右向左數(shù)1個空格，第2個空格里填“2”
|
|
最后補位
|
3 9 7 6 4 5 8 2 1
|
余下的空格填“1”
|
主要代碼如下：
/*
函數(shù)名稱：Permutation
函數(shù)功能：遞減進(jìn)位排列生成算法：輸出n個數(shù)的所有全排列
輸入變量：int n：1，2，3，...，n共n個自然數(shù)
輸出變量：無
*/
void Permutation(unsigned int n)
{
unsigned int *p
= new unsigned int[n];//用來存儲各個全排列的值，p[i]=i!
p[0] = 1;
for (int i=1; i<n;
i++)
{
p[i] = (i +
1) * p[i-1]; //cout << p[i] << " ";
}
int *b = new
int[n];//用來存儲新的全排列
int *yShe = new
int[n-1]; //將原中介數(shù)加上序號i的遞減進(jìn)位制數(shù)得到新的映射
int *diJ = new
int[n-1];
for (int i=0;
i<n-1; i++)
{
diJ[i] = yShe[i]
= 0;
}
diJ[n-2] = 1;
for (int c=0;
c<p[n-1]; c++)
{
DiJYingShe(yShe, diJ, n); //每次遞增1
for (int
i=0; i<n; i++) //新的全排列空格初始化
b[i] =
0;
int num =
n;
for (int
j=n-2; j>=0; j--) //獲取前n-1個數(shù)字
{
int s =
0;
int k =
n - 1;
while
(s < yShe[j])
{
if
(b[k] == 0) //該處未填數(shù)字
s++;
k--;
}
while
(b[k] != 0) //跳過已填數(shù)字
k--;
b[k] =
num--;
}
for (int
i=0; i<n; i++)//填充最后一個數(shù)字1
{
if
(b[i] == 0)
{
b[i] = 1;
break;
}
}
Print(b, n);
}
delete []b;
delete []p;
delete []diJ;
delete []yShe;
}
/*
函數(shù)名稱：DiJYingShe
函數(shù)功能：遞減進(jìn)位排列生成算法的加法運算：yShe[] += dZJ[]
輸入變量：int yShe[]：原遞減進(jìn)制中介數(shù)；
int diJ[]：遞減進(jìn)制數(shù)加數(shù)
int n：最大自然數(shù)n的值
輸出變量：int yShe[]：新的遞減進(jìn)制中介數(shù)
*/
void DiJYingShe(int yShe[], int diJ[], int n)
{
int pos = n -
2;
int r = 0;
while (pos
>= 0)
{
yShe[pos]
+= diJ[pos] + r;
if
(yShe[pos] >= pos + 2)
{
yShe[pos] -= pos + 2;
r = 1;
}
else
r = 0;
pos--;
}
}
循環(huán)左移排列生成算法
映射方法：循環(huán)左移排列生成算法與遞減進(jìn)位排列生成算法非常相似，同樣是在原始排列中找到比當(dāng)前數(shù)字小的數(shù)字個數(shù)。只不過循環(huán)左移使用的是左循環(huán)搜索法，而不是遞減進(jìn)位法使用的右側(cè)搜索。所謂左循環(huán)搜索法是指從起始數(shù)字開始向左搜索，如果到了左邊界還沒有發(fā)現(xiàn)終止數(shù)字，則從右邊界開始繼續(xù)尋找，直到終止數(shù)字被發(fā)現(xiàn)。
圖中展示了839647521種以開始數(shù)字為6，
結(jié)束數(shù)字為5和開始數(shù)字為7，結(jié)束數(shù)字為6的
左循環(huán)搜索區(qū)間，注意開始和結(jié)束數(shù)字是不包括
在區(qū)間內(nèi)的。
具體到循環(huán)左移的排列生成法的映射方法，
就是要為每一個數(shù)字確定這樣一個區(qū)間。方法是
以從9到2的順序依次產(chǎn)生中介數(shù)中的數(shù)字，中介數(shù)
從右向左產(chǎn)生（即原排列的9產(chǎn)生的數(shù)字放到中介數(shù)右數(shù)第一位，8產(chǎn)生的數(shù)字放到中介數(shù)右數(shù)第二位，以此類推。這樣才能得到遞減進(jìn)位制數(shù)）。對于9，產(chǎn)生的中介數(shù)字依然是9的右邊比9小的數(shù)字的個數(shù)。但是從8開始一直到2中的每一個數(shù)i，都是要做一個以i+1為開始數(shù)字，i為結(jié)束數(shù)字的左循環(huán)區(qū)間，并看這個左循環(huán)區(qū)間中比i小的數(shù)字的個數(shù)。例如對于排列839647521，9的右側(cè)比9小的數(shù)字有6個；9到8的左循環(huán)區(qū)間比8小的數(shù)字有1個；8到7的左循環(huán)區(qū)間比7小的數(shù)字有3 個；7到6的左循環(huán)區(qū)間比6小的數(shù)字有1個（如上面圖下半部所示）；6到5的左循環(huán)區(qū)間比5小的右3個數(shù)字（如上圖上半部分所示）；……；3到2的左循環(huán)區(qū)間里比2小的數(shù)字有1個。所以得到遞減中介數(shù)10031316（此中結(jié)束加上100的遞減進(jìn)制數(shù)131得新中介數(shù)10031447）
還原方法：循環(huán)左移的還原方法很自然。首先畫9個空格。當(dāng)拿到新的中介數(shù)后，從中介數(shù)的最右邊向左邊開始計數(shù)逐個計數(shù)。計數(shù)的方法是，對于中介數(shù)最右邊的數(shù)x9，從空格的最右端起數(shù)x9個空格，在第x9+1個空格上填上9。然后對于中介數(shù)的每一位xi，沿著左循環(huán)的方向數(shù)xi個未占用空格，在第xi+1個空格里填上i，即可完成還原。我給出了將中介數(shù)10031447還原的步驟，其中底紋代表為了定位下一個數(shù)字而數(shù)過的空格。紅色代表被填充的空格。最終得到結(jié)果592138647。
|
新中介數(shù)當(dāng)前位
|
新排列數(shù)
|
備注
|
|
初始
|
|
在還原前，畫9個空格
|
|
7
|
9
|
從右向左數(shù)7個空格，第8個空格提填“9”
|
|
4
|
9 8
|
從9開始左循環(huán)數(shù)4個空格，第5個空格提填“8”
|
|
4
|
9 8 7
|
從8開始左循環(huán)數(shù)4個空格，第5個空格提填“7”
|
|
1
|
9 8 6 79
|
從7開始左循環(huán)數(shù)1個空格，第2個空格提填“6”
|
|
3
|
5 9 8 6 79
|
從6開始左循環(huán)數(shù)3個空格，第4個空格提填“5”
|
|
0
|
5 9 8 6 4 77
|
從5開始左循環(huán)數(shù)0個空格，第1個空格提填“4”
|
|
0
|
5 9 3 8 6 4 77
|
從4開始左循環(huán)數(shù)0個空格，第1個空格提填“3”
|
|
1
|
5 9 2 3 8 6 4 77
|
從3開始左循環(huán)數(shù)1個空格，第2個空格提填“2”
|
|
最后補位
|
5 9 2 1 3 8 6 4 7
|
余下的空格填“1”
|
與遞減進(jìn)位排列生成算法一樣，循環(huán)左移排列生成算法也用到了遞減進(jìn)位排列生成算法的加法運算函數(shù)。主要代碼如下：
/*
函數(shù)名稱：Permutation
函數(shù)功能：循環(huán)左移排列生成算法：輸出n個數(shù)的所有全排列
輸入變量：int n：1，2，3，...，n共n個自然數(shù)
輸出變量：無
*/
void Permutation(unsigned int n)
{
unsigned int
*p = new unsigned int[n];//用來存儲各個全排列的值，p[i]=i!
p[0] = 1;
for (int
i=1; i<n; i++)
{
p[i] =
(i + 1) * p[i-1];
}
int *b = new
int[n];//用來存儲新的全排列
int *yShe =
new int[n-1]; //將原中介數(shù)加上序號i的遞減進(jìn)位制數(shù)得到新的映射
int *diJ =
new int[n-1];
for (int
i=0; i<n-1; i++)
{
diJ[i] =
yShe[i] = 0;
}
diJ[n-2] =
1;
for (int
c=0; c<p[n-1]; c++)
{
DiJYingShe(yShe, diJ, n); //每次遞增1
for (int i=0; i<n; i++) //新的全排列空格初始化
b[i]
= 0;
int num
= n;
int pos
= n - 1;
for (int
j=n-2; j>=0; j--) //獲取前n-1個數(shù)字
{
int
s = 0;
int
k = pos;
while (k >= 0 && s < yShe[j])
{
if (b[k] == 0) //該處未填數(shù)字
s++;
k--;
}
//跳過已填數(shù)字
while (k >= 0 && b[k] != 0)
k--;
if
(b[k] != 0)//如果到了最左側(cè)還沒有找到適合的位置，從最右側(cè)繼續(xù)分析
{
k = n - 1;
while (k > pos && b[k] != 0)//跳過非空位:b[j] == 0表示j位置是空位
k--;
}
//如果到了最左側(cè)還沒有找到適合的位置，從最右側(cè)繼續(xù)累積s
if
(s < yShe[j])
{
k = n - 1;
while (k >= 0 && s < yShe[j])
{
if (b[k] == 0)
s++;
k--;
}
while (k >= 0 && b[k] != 0) //跳過已填數(shù)字
k--;
}
b[k]
= num--;
pos
= k;
}
for (int
i=0; i<n; i++)//填充最后一個數(shù)字1
{
if
(b[i] == 0)
{
b[i] = 1;
break;
}
}
Print(b,
n);
}
delete []b;
delete []p;
delete
[]diJ;
delete
[]yShe;
}
最后介紹一種準(zhǔn)有序全排列生成算法：顛倒的協(xié)詞典順序算法。
這是Donald E.Knuth在《計算機程序設(shè)計藝術(shù)（第4卷 第2冊）》上介紹的一種方法。
該算法的原理為：設(shè)P是1～n的一個全排列:p = p1p2...pn
1）從排列的左端開始，找出第一個比右邊數(shù)字小的數(shù)字的序號j，即j = min{i | pi < pi+1}，如果j == n-1，表示已經(jīng)輸出了所有的全排列。
2）在pj的左邊的數(shù)字中，找出所有比pj小的數(shù)中最大的數(shù)字pk，即 k = max{i | pi > pj}（左邊的數(shù)從左至右是遞減的，因此k是所有小于pj的數(shù)字中序號最大者）
3）對換pj，pk
4）再將p1p2...pj-1倒轉(zhuǎn)得到新的排列
以n = 3為例，我們可以得到全排列123，213，132，312，231，321.
仔細(xì)觀察這些序列，如果我們從右到左地反射這些序列，就可以得到321，312，231，213，132，123。
它剛好是字典序全排列的顛倒。所以如果我們逆序地輸出序列，是可以得到一個有序全排列的。
代碼如下：
/*
函數(shù)名稱：Permutation
函數(shù)功能：顛倒的協(xié)詞典順序算法：逆序輸出n個數(shù)的所有全排列
輸入變量：int n：1，2，3，...，n共n個自然數(shù)
輸出變量：無
*/
void Permutation(unsigned int n)
{
int *a = new
int[n];//用來存儲n個自然數(shù)
for (int
i=0; i<n; i++) //存儲全排列的元素值，并計算全排列的數(shù)量
{
a[i] = i
+ 1;
}
int temp,
left, right;
while (1)
{
Print(a,
n);
for
(right=1; right<n; right++)//找出第一個比右邊數(shù)字小的數(shù)字的序號right-1
{
if
(a[right-1] < a[right])
break;
}
if
(right == n) //表示已經(jīng)輸出所有全排列
break;
//找到右邊界左邊數(shù)組中比a[right]小的最大的元素，這個就是要取代a[right]的元素
for
(left=0; a[left] >= a[right]; left++)
;
temp =
a[left]; a[left] = a[right]; a[right] = temp; //交換a[right]和a[left]
left =
0;
right--;
//右邊界減1，保證此時左右邊界之間的元素是一個遞減排列
while
(left < right)//逆置左右邊界之間的元素，使其按增序排列
{
temp = a[left]; a[left] = a[right];
a[right] = temp;
left++;
right--;
}
}
delete []a;
}
到這里我就把我目前所知的幾種非有序全排列算法都介紹完了，以下是上述七種方法的測試結(jié)果：（為了方便測試，我只要求輸出最后一個全排列）
當(dāng)n = 10 時，普通遞歸算法用時0秒；全排列循環(huán)移位法用時0秒；排列鄰位對換法用時0秒；遞增進(jìn)位排列生成算法用時3秒；遞減進(jìn)位排列生成算法用時3秒；循環(huán)左移排列生成算法用時4秒；顛倒的協(xié)詞典順序算法用時0秒。
當(dāng)n = 11 時，普通遞歸算法用時2秒；全排列循環(huán)移位法用時5秒；排列鄰位對換法用時2秒；遞增進(jìn)位排列生成算法用時42秒；遞減進(jìn)位排列生成算法用時39秒；循環(huán)左移排列生成算法用時54秒；顛倒的協(xié)詞典順序算法用時2秒。
當(dāng)n = 12時，普通遞歸算法用時29秒；排列鄰位對換法用時25秒；顛倒的協(xié)詞典順序算法用時23秒。
全排列的應(yīng)用非常廣泛，我們在很多地方都會遇到它，下次我將總結(jié)一下“列車出棧系列問題”，在該問題中，我們可以看到全排列的身影。
參考文獻(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
附錄：
《康托展開》：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
《非有序全排列生成算法集錦》
http://blog.csdn.net/goal00001111/archive/2009/01/20/3839683.aspx