使用C++實(shí)現(xiàn)全排列算法的方法詳解
<P>不論是哪種全排列生成算法，都遵循著“原排列”→“原中介數(shù)”→“新中介數(shù)”→“新排列”的過程。</P><P>其中中介數(shù)依據(jù)算法的不同會(huì)的到遞增進(jìn)位制數(shù)和遞減進(jìn)位制數(shù)。</P><P>關(guān)于排列和中介數(shù)的一一對應(yīng)性的證明我們不做討論，這里僅僅給出了排列和中介數(shù)的詳細(xì)映射方法。</P>
· 遞增進(jìn)位制和遞減進(jìn)位制數(shù)
所謂遞增進(jìn)位制和遞減進(jìn)位制數(shù)字是指數(shù)字的進(jìn)制隨著數(shù)字位置的不同遞增或遞減。通常我們見到的都是固定進(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)位制的道理是一樣的，只不過進(jìn)制從右向左依次是9、8、7、6……，正好與遞增進(jìn)位制相反。很明顯，遞減進(jìn)位制的一個(gè)最大的好處就是加法不易進(jìn)位，因?yàn)樗谶M(jìn)行加法最頻繁的末幾位里（最右邊）進(jìn)制比較大。
接下來要了解的是遞增進(jìn)位制、遞減進(jìn)位制數(shù)和其序號的關(guān)系。遞增、遞減進(jìn)位制數(shù)可以被看作一個(gè)有序的數(shù)字集合。如果規(guī)定遞增進(jìn)位制和遞減進(jìn)位制數(shù)的0的序號是十進(jìn)制0，遞增進(jìn)位制數(shù)的987654321和遞減進(jìn)位制數(shù)的123456789對應(yīng)十進(jìn)制序號362880（即9!），則可以整理一套對應(yīng)法則。其中，遞增進(jìn)位制數(shù)（a1 a2 a3 a4 a5 a6 a7 a8 a9）為：
a1*9! + a2*8! + ….+ a8*2! + a9*1! = 序號
例如序號100的遞增進(jìn)位制數(shù)就是4020，即4*4！+ 0*3！+ 2*2！+ 0*1！=100。將一個(gè)序號轉(zhuǎn)換成其遞增進(jìn)位制數(shù)首先需要找到一個(gè)比序號小的最大階乘數(shù)（即1、2、6、24、120、720……），對其進(jìn)行整數(shù)除得到遞增進(jìn)位制的第一位；將除法的余數(shù)反復(fù)應(yīng)用這個(gè)方法（當(dāng)然，之后選擇的余數(shù)是小一級的階乘數(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= 序號
例如序號100的遞減進(jìn)位制數(shù)就是131（a7 a8 a9， 即從后對齊），即 （1*8 + 3）*9 + 1 = 100。將一個(gè)序號轉(zhuǎn)換成其遞減進(jìn)位制數(shù)，需要對序號用9取余數(shù)，就可以得到遞減進(jìn)位制的最末位（這點(diǎn)和遞增進(jìn)位制先算出最高位相反）。用余下的數(shù)的整數(shù)除結(jié)果重復(fù)此過程（當(dāng)然，依次對8、7、6……取余），直到余數(shù)為0。
關(guān)于遞增進(jìn)位制和遞減進(jìn)位制需要注意的重點(diǎn)：一是其加減法的進(jìn)位需要小心；二是序號和數(shù)字的轉(zhuǎn)換。除了100之外，常見的轉(zhuǎn)換有：999的遞增數(shù)是121211，遞減數(shù)是1670；99的遞增數(shù)是4011，遞減數(shù)是130。大家可以以此為參考測試自己是否真正理解了計(jì)算的方法。下文將省略遞增進(jìn)位制或遞減進(jìn)位制的詳細(xì)計(jì)算過程。
從現(xiàn)在開始我們將詳細(xì)介紹六種排列生成算法。具體的理論介紹將被忽略，下文所注重的就是如何將排列映射為中介數(shù)以及如何將中介數(shù)還原為排列。
我全部以求839647521的下100個(gè)排列為例。
· 遞增進(jìn)位排列生成算法映射方法：將原排列按照從9到2的順序，依次查看其右側(cè)比其小的數(shù)字的個(gè)數(shù)。這個(gè)個(gè)數(shù)就是中介數(shù)的一位。例如對于原排列839647521。9的右側(cè)比9小的數(shù)字有6個(gè)，8的右側(cè)比8小的數(shù)字有7個(gè)，7的右側(cè)比7小的數(shù)字有3個(gè)，……2的右側(cè)比2小的數(shù)字有1個(gè)。最后得到遞增進(jìn)制中介數(shù)67342221。（此中介數(shù)加上100的遞增進(jìn)制數(shù)4020得到新的中介數(shù)67351311）
還原方法：我們設(shè)新中介數(shù)的位置號從左向右依次是9、8、7、6、5、4、3、2。在還原前，畫9個(gè)空格。對于每一個(gè)在位置x的中介數(shù)y，從空格的右側(cè)向左數(shù)y個(gè)未被占用的空格。在第y+1個(gè)未占用的空格中填上數(shù)字x。重復(fù)這個(gè)過程直到中介數(shù)中所有的位都被數(shù)完。最后在余下的最后一個(gè)空格里填上1，完成新排列的生成。以新中介數(shù)67351311為例，我給出了詳細(xì)的恢復(fù)步驟。其中紅色數(shù)字代表新填上的數(shù)字。最后得到新排列869427351。
void next_Permutations_by_increDecimal(int dataArr[],int size){
int i;
int *resultArr = new int[size];
int index = 0;
map<int,int>::iterator iter;
//第一步 求出中介數(shù)
//由大到小，得到并記錄當(dāng)前排列中，數(shù)字i的右邊比其小的數(shù)的個(gè)數(shù)
map<int,int> agentMap;
for(i=0; i<size; ++i){
agentMap.insert(valType(dataArr[i],count(dataArr,i,size,dataArr[i])));
}
qsort(dataArr,0,size-1);
//第二步 得到新的中介數(shù),在舊的中介數(shù)的基礎(chǔ)上，根據(jù)遞增進(jìn)位制數(shù)法加1
while (true){
++countNum;
next_inter_num(dataArr,agentMap);
//第三步 根據(jù)新的中介數(shù)得到新的排列
index = size -1;
//清空記錄當(dāng)前排列的數(shù)組，以存放新產(chǎn)生的排列
for(i=0; i<size; ++i){
resultArr[i] = 0;
}
while(true){
iter = agentMap.find(dataArr[index]);
valType value = *iter;
resultArr[getNextPosition(resultArr,size,value.second,0)] = dataArr[index];
--index;
if(index == 0) break;
}
//將最后一個(gè)空位置為最小數(shù)
i = 0;
while(true){
if(resultArr[i] != 0){
++i;
}else{
resultArr[i] = dataArr[index];
break;
}
}
print(resultArr,size);
bool flag = true;
for(i=1; i<size; ++i){
if(resultArr[i] > resultArr[i-1]){
flag = false;
break;
}
}
if(flag) break;
}
delete [] resultArr;
}
void next_inter_num(int dataArr[],map<int,int>& agentMap){
map<int,int>::iterator iter;
//temp當(dāng)前位需要增加得值，tmpResult為temp與當(dāng)前位的值之和，start為末位開始的進(jìn)制
int start = 2,temp=1,tmpResult;
int index = 1; //數(shù)組中的第一個(gè)數(shù)位最小數(shù)
while(true){
iter = agentMap.find(dataArr[index]);
valType value = *iter;
tmpResult = value.second + temp;
if(tmpResult < start){
//已經(jīng)不產(chǎn)生進(jìn)位
agentMap.erase(dataArr[index]);
agentMap.insert(valType(dataArr[index],tmpResult));
break;
}else{
agentMap.erase(dataArr[index]);
agentMap.insert(valType(dataArr[index],tmpResult % start));
temp = tmpResult / start;
++start;
}
++index;
}
}
· 遞減進(jìn)位排列生成算法
映射方法：遞減進(jìn)位制的映射方法剛好和遞增進(jìn)位制相反，即按照從9到2的順序，依次查看其右側(cè)比其小數(shù)字的個(gè)數(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)行依次計(jì)數(shù)填空。例如對于新中介數(shù)12224527，我給出了詳細(xì)的還原步驟。紅色代表當(dāng)前正在填充的空格。最終得到新排列397645821。
C++實(shí)現(xiàn)代碼：
void next_Permutations_by_DecreDecimal(int dataArr[],int size){
//創(chuàng)建一個(gè)結(jié)果數(shù)組，用來記錄下一個(gè)排列
int *resultArr = new int[size];
int i;
//第一步 求出中介數(shù)
map<int,int> agentMap;
for(i=0; i<size; ++i){
int nums = count(dataArr,i,size,dataArr[i]);
agentMap.insert(valType(dataArr[i],nums));
}
//第二步 求新的中介數(shù) 此處最低位進(jìn)制最高，故不會(huì)頻繁產(chǎn)生進(jìn)位，性能應(yīng)該優(yōu)于遞增進(jìn)位
//最低位進(jìn)制為9，向前依次遞減
int start = size,temp = 1;
int tmpResult;
int index = size-1;//中介數(shù)末位數(shù)位數(shù)字序列中最大的數(shù)右邊比其小的數(shù)
map<int,int>::iterator iter;
qsort(dataArr,0,size-1);
while (true){
++countNum; //全局變量 記錄排列個(gè)數(shù)
next_inter_num(dataArr,agentMap,size);
index = size -1;
//第三步 根據(jù)產(chǎn)生的中介數(shù)得到新的排列
for(i=0; i<size; ++i){
resultArr[i] = 0;
}
while(true){
iter = agentMap.find(dataArr[index]);
valType value = *iter;
//找到下一個(gè)填充空位
resultArr[getNextPosition(resultArr,size,value.second,0)] = dataArr[index];
--index;
if(index == 0) break;
}
i = 0;
while(true){
if(resultArr[i] != 0){
++i;
}else{
resultArr[i] = dataArr[index];
break;
}
}
print(resultArr,size);
bool flag = true;
for(i=1; i<size; ++i){
if(resultArr[i] > resultArr[i-1]){
flag = false;
break;
}
}
if(flag) break;
}
delete [] resultArr;
}
void next_inter_num(int dataArr[],map<int,int> &agentMap,int size){
int start = size,temp = 1;
int tmpResult;
int index = size-1;//中介數(shù)末位數(shù)位數(shù)字序列中最大的數(shù)右邊比其小的數(shù)
map<int,int>::iterator iter;
while(true){
iter = agentMap.find(dataArr[index]);
valType value = *iter;
tmpResult = value.second + temp;
if(tmpResult < start){
//沒有產(chǎn)生進(jìn)位，直接改寫末位值
agentMap.erase(dataArr[index]);
agentMap.insert(valType(dataArr[index],tmpResult));
break;
}else{
//產(chǎn)生進(jìn)位
agentMap.erase(dataArr[index]);
agentMap.insert(valType(dataArr[index],tmpResult % start));
tmpResult = tmpResult / start;
--start;
}
--index;
}
}
· 字典全排列生成法
映射方法：將原排列數(shù)字從左到右（最末尾不用理會(huì)），依次查看數(shù)字右側(cè)比其小的數(shù)字有幾個(gè)，個(gè)數(shù)就是中介數(shù)的一位。例如，對于排列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)進(jìn)制數(shù)4020后得到新中介數(shù)72652011）
還原方法：還原方法為映射方法的逆過程。你可以先寫出輔助數(shù)字1 2 3 4 5 6 7 8 9，以及9個(gè)空位用于填充新排列。然后從新中介數(shù)的最高位數(shù)起。例如新中介數(shù)最高位是x，你就可以從輔助數(shù)字的第一個(gè)沒有被使用的數(shù)字開始數(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ù)到一。第y+1個(gè)數(shù)字就是下一個(gè)空位的數(shù)字。我們將此數(shù)字標(biāo)為“已用”，然后用其填充左起第二個(gè)空位。依此類推，直到最后一個(gè)中介數(shù)中的數(shù)字被數(shù)完為止。例如對于新中介數(shù)72652011，我們給出其輔助數(shù)字和空位的每一步的情況。其中紅色的數(shù)字代表“正在標(biāo)記為已用”，“已用”的數(shù)字不會(huì)再被算在之后的計(jì)數(shù)當(dāng)中。當(dāng)新中介數(shù)中所有的數(shù)字都被數(shù)完了，輔助數(shù)字中剩下的唯一數(shù)字將被填入最后的空位中。最終得到新排列839741562。
C++實(shí)現(xiàn)：
void next_Permutations_by_DicOrder(int dataArr[],int size){
int key = 0;
int index,temp,end,left,right;
int i;
bool flag ;
while(true){
++countNum;
print(dataArr,size);
flag = true;
index = 0,temp = 0,end=8,left = right = 0;
//從當(dāng)前排列末尾向前找到第一次出現(xiàn)下降的點(diǎn)
for(i = size-1; i > 0; i--){
if(dataArr[i] > dataArr[i-1]){
key = i-1; //K記錄下降的點(diǎn)
flag = false;
break;
}
}
//如果已經(jīng)是由高到低有序，則操作完成
if(flag)
break;
index = key + 1;
//找到后綴中比第一次下降點(diǎn)的數(shù)大的數(shù)中最小的數(shù)
while(dataArr[key] < dataArr[index] && index < size){
++index;
}
index --;
//將找到的數(shù)和第一次出現(xiàn)下降的點(diǎn)交換
temp = dataArr[key];
dataArr[key] = dataArr[index];
dataArr[index] = temp;
left = key+1;
right = size - 1;
//將下降點(diǎn)后面的數(shù)逆轉(zhuǎn)
while(left < right){
temp = dataArr[left];
dataArr[left] = dataArr[right];
dataArr[right] = temp;
++left;
--right;
}
}
}
回溯法：
void next_Permutations_by_backtrack(int dataArr[],int size){
//創(chuàng)建結(jié)果數(shù)組
int *resultArr = new int[size+1];
backTrack(1,size+1,resultArr,dataArr);
delete [] resultArr;
}
//剪枝函數(shù)
bool place(int k,int resultArr[])
{
for (int j = 1; j < k; j++) {
if (resultArr[j] == resultArr[k]) {
return false;
}
}
return true;
}
void backTrack(int t,int size,int resultArr[],int dataArr[])
{
if (t > size-1) {
++ countNum;
for(int i = 1; i < size; i++) {
cout << resultArr[i] << " ";
}
cout << endl;
} else {
for(int i = 1; i < size; i++) {
resultArr[t] = dataArr[i-1];
if (place(t,resultArr)) {
backTrack(t+1,size,resultArr,dataArr);
}
}
}
}
相關(guān)文章
這篇文章主要介紹了c++查詢最短路徑示例,需要的朋友可以參考下2014-05-05
LintCode-排序列表轉(zhuǎn)換為二分查找樹分析及實(shí)例
這篇文章主要介紹了LintCode-排序列表轉(zhuǎn)換為二分查找樹分析及實(shí)例的相關(guān)資料,需要的朋友可以參考下2017-04-04
這篇文章并不是一個(gè)綜合的手冊，而是一個(gè)C++中各種內(nèi)存分配方法的概述。它面向已經(jīng)很熟悉C++語言的讀者2013-09-09
這篇文章主要為大家詳細(xì)介紹C++?Queue隊(duì)列類模版實(shí)例，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要給大家介紹了關(guān)于C++運(yùn)算符重載的一些困惑，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
這篇文章主要為大家詳細(xì)介紹了用C語言實(shí)現(xiàn)掃雷小程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
C++設(shè)計(jì)模式之備忘錄模式（Memento）
這篇文章主要為大家詳細(xì)介紹了C++設(shè)計(jì)模式之備忘錄模式Memento的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-04-04
c語言使用fdk_aac實(shí)現(xiàn)aac音頻解碼為pcm
這篇文章主要為大家詳細(xì)介紹了c語言如何使用fdk_aac庫實(shí)現(xiàn)aac音頻解碼為pcm的功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-11-11
使用C語言遞歸與非遞歸實(shí)現(xiàn)字符串反轉(zhuǎn)函數(shù)char *reverse(char *str)的方法
本篇文章是對使用C語言遞歸與非遞歸實(shí)現(xiàn)字符串反轉(zhuǎn)函數(shù)char *reverse(char *str)進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
數(shù)組中求第K大數(shù)的實(shí)現(xiàn)方法
本篇文章是對數(shù)組中求第K大數(shù)的實(shí)現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05