使用C++實現全排列算法的方法詳解

2020-02-24 14:28:03

字體：大中小

來源：轉載

供稿：網友

全排列算法的遞歸和非遞歸實現是一種常用的算法，用于尋找序列的全置換，本文是武林技術頻道小編為大家帶來的使用C++實現全排列算法的方法詳解，一起來了解一下吧！
·?遞增進位制和遞減進位制數?
所謂遞增進位制和遞減進位制數字是指數字的進制隨著數字位置的不同遞增或遞減。通常我們見到的都是固定進制數字，如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（a7?a8?a9，?即從后對齊），即?（1*8?+?3）*9?+?1?=?100。將一個序號轉換成其遞減進位制數，需要對序號用9取余數，就可以得到遞減進位制的最末位（這點和遞增進位制先算出最高位相反）。用余下的數的整數除結果重復此過程（當然，依次對8、7、6……取余），直到余數為0。?

關于遞增進位制和遞減進位制需要注意的重點：一是其加減法的進位需要小心；二是序號和數字的轉換。除了100之外，常見的轉換有：999的遞增數是121211，遞減數是1670；99的遞增數是4011，遞減數是130。大家可以以此為參考測試自己是否真正理解了計算的方法。下文將省略遞增進位制或遞減進位制的詳細計算過程。

從現在開始我們將詳細介紹六種排列生成算法。具體的理論介紹將被忽略，下文所注重的就是如何將排列映射為中介數以及如何將中介數還原為排列。

我全部以求839647521的下100個排列為例。

·?遞增進位排列生成算法
映射方法：將原排列按照從9到2的順序，依次查看其右側比其小的數字的個數。這個個數就是中介數的一位。例如對于原排列839647521。9的右側比9小的數字有6個，8的右側比8小的數字有7個，7的右側比7小的數字有3個，……2的右側比2小的數字有1個。最后得到遞增進制中介數67342221。（此中介數加上100的遞增進制數4020得到新的中介數67351311）

還原方法：我們設新中介數的位置號從左向右依次是9、8、7、6、5、4、3、2。在還原前，畫9個空格。對于每一個在位置x的中介數y，從空格的右側向左數y個未被占用的空格。在第y+1個未占用的空格中填上數字x。重復這個過程直到中介數中所有的位都被數完。最后在余下的最后一個空格里填上1，完成新排列的生成。以新中介數67351311為例，我給出了詳細的恢復步驟。其中紅色數字代表新填上的數字。最后得到新排列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;
??? //第一步 求出中介數
?//由大到小，得到并記錄當前排列中，數字i的右邊比其小的數的個數
??? 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);
??? //第二步 得到新的中介數,在舊的中介數的基礎上，根據遞增進位制數法加1
? while (true){
???? ++countNum;
???? next_inter_num(dataArr,agentMap);
???? //第三步 根據新的中介數得到新的排列
???? index = size -1;
???? //清空記錄當前排列的數組，以存放新產生的排列
???? 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;
???? }
???? //將最后一個空位置為最小數
???? 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當前位需要增加得值，tmpResult為temp與當前位的值之和，start為末位開始的進制
??? int start = 2,temp=1,tmpResult;
??? int index = 1; //數組中的第一個數位最小數
?while(true){
?? iter = agentMap.find(dataArr[index]);
?? valType value = *iter;
?? tmpResult = value.second + temp;
?? if(tmpResult < start){
??? //已經不產生進位
??? ??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;
?}
}

·?遞減進位排列生成算法
映射方法：遞減進位制的映射方法剛好和遞增進位制相反，即按照從9到2的順序，依次查看其右側比其小數字的個數。但是，生成中介數的順序不再是從左向右，而是從右向左。生成的遞減進制中介數剛好是遞增進位排列生成算法得到中介數的鏡像。例如839647521的遞減進制中介數就是12224376。（此中介數加上100的遞減進制數131后得到新中介數12224527）?

還原方法：遞減進位制中介數的還原方法也剛好和遞增進位制中介數相反。遞增進位制還原方法是按照從中介數最高位（左側）到最低位（右側）的順序來填數。而遞減僅位置還原方法則從中介數的最低位向最高位進行依次計數填空。例如對于新中介數12224527，我給出了詳細的還原步驟。紅色代表當前正在填充的空格。最終得到新排列397645821。

C++實現代碼：

void next_Permutations_by_DecreDecimal(int dataArr[],int size){
?//創建一個結果數組，用來記錄下一個排列
?int *resultArr = new int[size];
?int i;
??? //第一步 求出中介數
??? map<int,int> agentMap;
?for(i=0; i<size; ++i){
??? int nums = count(dataArr,i,size,dataArr[i]);
??? agentMap.insert(valType(dataArr[i],nums));
?}
?//第二步 求新的中介數 此處最低位進制最高，故不會頻繁產生進位，性能應該優于遞增進位
?//最低位進制為9，向前依次遞減
?int start = size,temp = 1;
?int tmpResult;
?int index = size-1;//中介數末位數位數字序列中最大的數右邊比其小的數
?map<int,int>::iterator iter;
?qsort(dataArr,0,size-1);
?while (true){
?? ++countNum; //全局變量 記錄排列個數
???????? next_inter_num(dataArr,agentMap,size);
?? index = size -1;
??//第三步 根據產生的中介數得到新的排列
??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;
??? }
??? 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;//中介數末位數位數字序列中最大的數右邊比其小的數
?map<int,int>::iterator iter;
??? while(true){
?? iter = agentMap.find(dataArr[index]);
?? valType value = *iter;
?? tmpResult = value.second + temp;
?? if(tmpResult < start){
???//沒有產生進位，直接改寫末位值
??? ??agentMap.erase(dataArr[index]);
???agentMap.insert(valType(dataArr[index],tmpResult));
???break;
?? }else{?
???//產生進位
???agentMap.erase(dataArr[index]);
???agentMap.insert(valType(dataArr[index],tmpResult % start));
???tmpResult = tmpResult / start;
???--start;
?? }?
?? --index;
?}
}

·?字典全排列生成法
映射方法：將原排列數字從左到右（最末尾不用理會），依次查看數字右側比其小的數字有幾個，個數就是中介數的一位。例如，對于排列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，從輔助數字的第一個未用數字數起，數到一。第y+1個數字就是下一個空位的數字。我們將此數字標為“已用”，然后用其填充左起第二個空位。依此類推，直到最后一個中介數中的數字被數完為止。例如對于新中介數72652011，我們給出其輔助數字和空位的每一步的情況。其中紅色的數字代表“正在標記為已用”，“已用”的數字不會再被算在之后的計數當中。當新中介數中所有的數字都被數完了，輔助數字中剩下的唯一數字將被填入最后的空位中。最終得到新排列839741562。

C++實現：

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;
??//從當前排列末尾向前找到第一次出現下降的點
??for(i = size-1; i > 0; i--){
???if(dataArr[i] > dataArr[i-1]){
????key = i-1; //K記錄下降的點
????flag = false;
????break;
???}???
??}
??//如果已經是由高到低有序，則操作完成
??if(flag)
???break;
??index = key + 1;
??????? //找到后綴中比第一次下降點的數大的數中最小的數
??while(dataArr[key] < dataArr[index] && index < size){
????? ++index;
??}
??????? index --;
??//將找到的數和第一次出現下降的點交換
??temp = dataArr[key];
??dataArr[key] = dataArr[index];
??dataArr[index] = temp;
??left = key+1;
??right = size - 1;
??//將下降點后面的數逆轉
??while(left < right){
???temp = dataArr[left];
???dataArr[left] = dataArr[right];
???dataArr[right] = temp;
???++left;
???--right;
??}
?}
}

回溯法：

void next_Permutations_by_backtrack(int dataArr[],int size){
?//創建結果數組
??? int *resultArr = new int[size+1];
?backTrack(1,size+1,resultArr,dataArr);
?delete [] resultArr;
}
//剪枝函數
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);
???}
??}
?}
}