字符串的全排列和組合算法

全排列在筆試面試中很熱門，因為它難度適中，既可以考察遞歸實現，又能進一步考察非遞歸的實現，便于區分出考生的水平。所以在百度和迅雷的校園招聘以及程序員和軟件設計師的考試中都考到了，因此本文對全排列作下總結幫助大家更好的學習和理解。對本文有任何補充之處，歡迎大家指出。

首先來看看題目是如何要求的（百度迅雷校招筆試題）。

（轉載：http://blog.csdn.net/hackbuteer1/article/details/7462447）

一、字符串的排列
用C++寫一個函數, 如 Foo(const char *str), 打印出 str 的全排列,
如 abc 的全排列: abc, acb, bca, dac, cab, cba

一、全排列的遞歸實現

為方便起見，用123來示例下。123的全排列有123、132、213、231、312、321這六種。首先考慮213和321這二個數是如何得出的。顯然這二個都是123中的1與后面兩數交換得到的。然后可以將123的第二個數和每三個數交換得到132。同理可以根據213和321來得231和312。因此可以知道——全排列就是從第一個數字起每個數分別與它后面的數字交換。找到這個規律后，遞歸的代碼就很容易寫出來了：

#include<iostream>
using namespace std;
#include<assert.h>void Permutation(char* pStr, char* pBegin)
{assert(pStr && pBegin);if(*pBegin == '\0')printf("%s\n",pStr);else{for(char* pCh = pBegin; *pCh != '\0'; pCh++){swap(*pBegin,*pCh);Permutation(pStr, pBegin+1);swap(*pBegin,*pCh);}}
}int main(void)
{char str[] = "abc";Permutation(str,str);return 0;
}
另外一種寫法： 
</pre><pre name="code" class="cpp"><pre name="code" class="cpp">//k表示當前選取到第幾個數，m表示共有多少個數
#include <iostream>
#include <cstring>
#include <cassert>
using namespace std;
void Permutation(char* pStr,int k,int m)
{assert(pStr);if(k == m){static int num = 1;  //局部靜態變量，用來統計全排列的個數printf("第%d個排列\t%s\n",num++,pStr);}else{for(int i = k; i < m; i++){swap(*(pStr+k),*(pStr+i));Permutation(pStr, k + 1 , m);swap(*(pStr+k),*(pStr+i));}}
}int main(void)
{char str[] = "abc";Permutation(str , 0 , strlen(str));return 0;
}


 
如果字符串中有重復字符的話，上面的那個方法肯定不會符合要求的，因此現在要想辦法來去掉重復的數列。

 
二、去掉重復的全排列的遞歸實現

 
由于全排列就是從第一個數字起每個數分別與它后面的數字交換。我們先嘗試加個這樣的判斷——如果一個數與后面的數字相同那么這二個數就不交換了。如122，第一個數與后面交換得212、221。然后122中第二數就不用與第三個數交換了，但對212，它第二個數與第三個數是不相同的，交換之后得到221。與由122中第一個數與第三個數交換所得的221重復了。所以這個方法不行。

 

 
換種思維，對122，第一個數1與第二個數2交換得到212，然后考慮第一個數1與第三個數2交換，此時由于第三個數等于第二個數，所以第一個數不再與第三個數交換。再考慮212，它的第二個數與第三個數交換可以得到解決221。此時全排列生成完畢。

 
這樣我們也得到了在全排列中去掉重復的規則——去重的全排列就是從第一個數字起每個數分別與它后面非重復出現的數字交換。下面給出完整代碼： 

 

 #include<iostream>using namespace std;#include<assert.h>//在[nBegin,nEnd)區間中是否有字符與下標為pEnd的字符相等,也就是在pEnd之前是否有與之相等的數bool IsSwap(char* pBegin , char* pEnd){char *p;for(p = pBegin ; p < pEnd ; p++){if(*p == *pEnd)return false;}return true;}void Permutation(char* pStr , char *pBegin){assert(pStr);if(*pBegin == '\0'){static int num = 1; ?//局部靜態變量，用來統計全排列的個數printf("第%d個排列\t%s\n",num++,pStr);}else{for(char *pCh = pBegin; *pCh != '\0'; pCh++) ? //第pBegin個數分別與它后面的數字交換就能得到新的排列 ??{if(IsSwap(pBegin , pCh)){swap(*pBegin , *pCh);Permutation(pStr , pBegin + 1);swap(*pBegin , *pCh);}}}}int main(void){char str[] = "baa";Permutation(str , str);return 0;}OK，到現在我們已經能熟練寫出遞歸的方法了，并且考慮了字符串中的重復數據可能引發的重復數列問題。那么如何使用非遞歸的方法來得到全排列了？三、全排列的非遞歸實現要考慮全排列的非遞歸實現，先來考慮如何計算字符串的下一個排列。如"1234"的下一個排列就是"1243"。只要對字符串反復求出下一個排列，全排列的也就迎刃而解了。如何計算字符串的下一個排列了？來考慮"926520"這個字符串，我們從后向前找第一雙相鄰的遞增數字，"20"、"52"都是非遞增的，"26 "即滿足要求，稱前一個數字2為替換數，替換數的下標稱為替換點，再從后面找一個比替換數大的最小數（這個數必然存在），0、2都不行，5可以，將5和2交換得到"956220"，然后再將替換點后的字符串"6220"顛倒即得到"950226"。對于像“4321”這種已經是最“大”的排列，采用STL中的處理方法，將字符串整個顛倒得到最“小”的排列"1234"并返回false。
 

 這樣，只要一個循環再加上計算字符串下一個排列的函數就可以輕松的實現非遞歸的全排列算法。按上面思路并參考STL中的實現源碼，不難寫成一份質量較高的代碼。值得注意的是在循環前要對字符串排序下，可以自己寫快速排序的代碼（請參閱《白話經典算法之六 快速排序 快速搞定》），也可以直接使用VC庫中的快速排序函數（請參閱《使用VC庫函數中的快速排序函數》）。下面列出完整代碼：
 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#include<assert.h>//反轉區間
void Reverse(char* pBegin , char* pEnd)
{while(pBegin < pEnd)swap(*pBegin++ , *pEnd--);
}
//下一個排列
bool Next_permutation(char a[])
{assert(a);char *p , *q , *pFind;char *pEnd = a + strlen(a) - 1;if(a == pEnd)return false;p = pEnd;while(p != a){q = p;p--;if(*p < *q)  //找降序的相鄰2數,前一個數即替換數  {//從后向前找比替換點大的第一個數pFind = pEnd;while(*pFind < *p)--pFind;swap(*p , *pFind);//替換點后的數全部反轉Reverse(q , pEnd);return true;}}Reverse(a , pEnd);   //如果沒有下一個排列,全部反轉后返回false   return false;
}int cmp(const void *a,const void *b)
{return int(*(char *)a - *(char *)b);
}
int main(void)
{char str[] = "bac";int num = 1;qsort(str , strlen(str),sizeof(char),cmp);do{printf("第%d個排列\t%s\n",num++,str); }while(Next_permutation(str));return 0;
}


 

 

 至此我們已經運用了遞歸與非遞歸的方法解決了全排列問題，總結一下就是：
 1、全排列就是從第一個數字起每個數分別與它后面的數字交換。
 2、去重的全排列就是從第一個數字起每個數分別與它后面非重復出現的數字交換。
 3、全排列的非遞歸就是由后向前找替換數和替換點，然后由后向前找第一個比替換數大的數與替換數交換，最后顛倒替換點后的所有數據。
 
 

 二、字符串的組合
 
 

 題目：輸入一個字符串，輸出該字符串中字符的所有組合。舉個例子，如果輸入abc，它的組合有a、b、c、ab、ac、bc、abc。
 
上面我們詳細討論了如何用遞歸的思路求字符串的排列。同樣，本題也可以用遞歸的思路來求字符串的組合。
 
 假設我們想在長度為n的字符串中求m個字符的組合。我們先從頭掃描字符串的第一個字符。針對第一個字符，我們有兩種選擇：第一是把這個字符放到組合中去，接下來我們需要在剩下的n-1個字符中選取m-1個字符；第二是不把這個字符放到組合中去，接下來我們需要在剩下的n-1個字符中選擇m個字符。這兩種選擇都很容易用遞歸實現。下面是這種思路的參考代碼：

 

 
 

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#include<assert.h>void Combination(char *string ,int number,vector<char> &result);void Combination(char *string)
{assert(string != NULL);vector<char> result;int i , length = strlen(string);for(i = 1 ; i <= length ; ++i)Combination(string , i ,result);
}void Combination(char *string ,int number , vector<char> &result)
{assert(string != NULL);if(number == 0){static int num = 1;printf("第%d個組合\t",num++);vector<char>::iterator iter = result.begin();for( ; iter != result.end() ; ++iter)printf("%c",*iter);printf("\n");return ;}if(*string == '\0')return ;result.push_back(*string);Combination(string + 1 , number - 1 , result);result.pop_back();Combination(string + 1 , number , result);
}int main(void)
{char str[] = "abc";Combination(str);return 0;
}


 
由于組合可以是1個字符的組合，2個字符的字符……一直到n個字符的組合，因此在函數void Combination(char* string)，我們需要一個for循環。另外，我們用一個vector來存放選擇放進組合里的字符。

 
方法二：用位運算來實現求組合 

 

 

#include<iostream>
using namespace std;int a[] = {1,3,5,4,6};
char str[] = "abcde";void print_subset(int n , int s)
{printf("{");for(int i = 0 ; i < n ; ++i){if( s&(1<<i) )         // 判斷s的二進制中哪些位為1，即代表取某一位printf("%c ",str[i]);   //或者a[i]}printf("}\n");
}void subset(int n)
{for(int i= 0 ; i < (1<<n) ; ++i){print_subset(n,i);}
}int main(void)
{subset(5);return 0;
}


 

字符串全排列擴展----八皇后問題題目：在8×8的國際象棋上擺放八個皇后，使其不能相互攻擊，即任意兩個皇后不得處在同一行、同一列或者同一對角斜線上。下圖中的每個黑色格子表示一個皇后，這就是一種符合條件的擺放方法。請求出總共有多少種擺法。這就是有名的八皇后問題。解決這個問題通常需要用遞歸，而遞歸對編程能力的要求比較高。因此有不少面試官青睞這個題目，用來考察應聘者的分析復雜問題的能力以及編程的能力。由于八個皇后的任意兩個不能處在同一行，那么這肯定是每一個皇后占據一行。于是我們可以定義一個數組ColumnIndex[8]，數組中第i個數字表示位于第i行的皇后的列號。先把ColumnIndex的八個數字分別用0-7初始化，接下來我們要做的事情就是對數組ColumnIndex做全排列。由于我們是用不同的數字初始化數組中的數字，因此任意兩個皇后肯定不同列。我們只需要判斷得到的每一個排列對應的八個皇后是不是在同一對角斜線上，也就是數組的兩個下標i和j，是不是i-j==ColumnIndex[i]-Column[j]或者j-i==ColumnIndex[i]-ColumnIndex[j]。關于排列的詳細討論，詳見上面的講解。
接下來就是寫代碼了。思路想清楚之后，編碼并不是很難的事情。下面是一段參考代碼：


 

#include<iostream>
using namespace std;int g_number = 0;
void Permutation(int * , int  , int );
void Print(int * , int );void EightQueen( )
{const int queens = 8;int ColumnIndex[queens];for(int i = 0 ; i < queens ; ++i)ColumnIndex[i] = i;    //初始化Permutation(ColumnIndex , queens , 0);
}bool Check(int ColumnIndex[] , int length)
{int i,j;for(i = 0 ; i < length; ++i){for(j = i + 1 ; j < length; ++j){if( i - j == ColumnIndex[i] - ColumnIndex[j] || j - i == ColumnIndex[i] - ColumnIndex[j])   //在正、副對角線上return false;}}return true;
}
void Permutation(int ColumnIndex[] , int length , int index)
{if(index == length){if( Check(ColumnIndex , length) )   //檢測棋盤當前的狀態是否合法{++g_number;Print(ColumnIndex , length);}}else{for(int i = index ; i < length; ++i)   //全排列{swap(ColumnIndex[index] , ColumnIndex[i]);Permutation(ColumnIndex , length , index + 1);swap(ColumnIndex[index] , ColumnIndex[i]);}}
}void Print(int ColumnIndex[] , int length)
{printf("%d\n",g_number);for(int i = 0 ; i < length; ++i)printf("%d ",ColumnIndex[i]);printf("\n");
}int main(void)
{EightQueen();return 0;
}


 
轉載：http://zhedahht.blog.163.co

 

 

 題目：輸入兩個整數n和m，從數列1,2,3...n中隨意取幾個數，使其和等于m，要求列出所有的組合。
 

#include <iostream>
#include <list>
using namespace std;
list<int> list1;
void find_factor(int sum,int n)
{//遞歸出口if(n<=0||sum<=0)return;//輸出找到的數if(sum==n){list1.reverse();for(list<int>::iterator iter=list1.begin();iter!=list1.end();iter++)cout<<*iter<<"+";cout<<n<<endl;list1.reverse();}list1.push_front(n);find_factor(sum-n,n-1);//n放在里面list1.pop_front();find_factor(sum,n-1);//n不放在里面
}int main(void)
{int sum,n;cin>>sum>>n;cout<<"所有可能的序列，如下："<<endl;find_factor(sum,n);return 0;
}


 

 

 
 
 











本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。

如若轉載，請注明出處：http://www.pswp.cn/news/259346.shtml


繁體地址，請注明出處：http://hk.pswp.cn/news/259346.shtml

英文地址，請注明出處：http://en.pswp.cn/news/259346.shtml


如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！











相關文章










設計模式基于C#的工程化實現及擴展








設計模式基于C#的工程化實現及擴展




設計模式基于C#的工程化實現及擴展 轉載于:https://www.cnblogs.com/gzmg/p/3344833.html




閱讀更多...

















Python實現atm機的功能








Python實現atm機的功能




主要還是參考網上內容&#xff0c;自己做了修改。雖然代碼有小bug&#xff0c;但是不影響學習和測試。功能&#xff1a;1.額度&#xff1a;80002.可以提現&#xff0c;手續費5%3.每月最后一天出賬單&#xff0c;寫入文件4.記錄每月日常消費流水5.提供還款接口1.atm的腳本[rootp…




閱讀更多...

















Direct ByteBuffer學習








Direct ByteBuffer學習




ByteBuffer有兩種一種是heap ByteBuffer,該類對象分配在JVM的堆內存里面&#xff0c;直接由Java虛擬機負責垃圾回收&#xff0c;一種是direct ByteBuffer是通過jni在虛擬機外內存中分配的。通過jmap無法查看該快內存的使用情況。只能通過top來看它的內存使用情況。 JVM堆內存大…




閱讀更多...

















魔獸爭霸Ⅲ運行時不能初始化directX的錯誤解決








魔獸爭霸Ⅲ運行時不能初始化directX的錯誤解決




運行魔獸爭霸3不能初始化DirectX錯誤這樣解決&#xff1a; 1&#xff1a;在運行中輸入(winr)&#xff1a;dxdiag&#xff0c;查看顯示欄&#xff0c;確定電腦已安裝好directx 8.1以上&#xff0c;且下面的三個加速都已開啟。 2&#xff1a;如果沒有安裝directx就下載安裝一個&a…




閱讀更多...

















Android7.0占用空間,Android7.0 開發者注意事項








Android7.0占用空間,Android7.0 開發者注意事項




1、當設備處于充電狀態且屏幕已關閉一定時間后&#xff0c;設備會進入低電耗模式并應用第一部分限制&#xff1a;關閉應用網絡訪問、推遲作業和同步。如果進入低電耗模式后設備處于靜止狀態達到一定時間&#xff0c;系統則會對 PowerManager.WakeLock、AlarmManager 鬧鈴、GPS …




閱讀更多...

















Android探索之旅 | 面向對象和Java基礎








Android探索之旅 | 面向對象和Java基礎




-- 作者 謝恩銘 轉載請注明出處 上一篇 Android探索之旅 | Android簡介 中說到&#xff1a; "Android的默認開發語言是Java&#xff0c;入門簡單。而且&#xff0c;你的Java水平不需要多好就可以上手開發Android App了。" 不少朋友說看到后很是心安。 不過小編也不想…




閱讀更多...

















DataGirdView 編輯項時的驗證








DataGirdView 編輯項時的驗證




dgvConfig.DataSource  CreateTable();dgvConfig.Columns["編號"].ReadOnly  true; //只讀dgvConfig.AllowUserToAddRows  false;  //不允許添加新行dgvConfig.EditingControlShowing  new DataGridViewEditingControlShowingEventHandler(dgvConfig_EditingControlS…




閱讀更多...

















使用Vitamio打造自己的Android萬能播放器（7）——在線播放（下載視頻）








使用Vitamio打造自己的Android萬能播放器（7）——在線播放（下載視頻）




前言 本章將實現非常實用的功能——下載在線視頻。涉及到多線程、線程更新UI等技術&#xff0c;還需思考產品的設計&#xff0c;如何將新加的功能更好的融入到現有的產品中&#xff0c;并不是簡單的加一個界面就行了&#xff0c;歡迎大家交流產品設計和技術細節實現&#xff01…




閱讀更多...

















生成0到1之間隨機數的C代碼








生成0到1之間隨機數的C代碼




#include <stdlib.h>#include <stdio.h>#include <time.h>int main(){srand((unsigned)time(NULL));int i;double r;for(i0;i<50;i){r(float)rand()/RAND_MAX; printf("%f\n",r);}return 0;}




閱讀更多...

















HTML聲明文檔類型后樣式出錯,doctype如何聲明








HTML聲明文檔類型后樣式出錯,doctype如何聲明




如何doctype聲明&#xff0c;新增的結構元素和功能元素HTML5已形成了最終的標準&#xff0c;概括來講&#xff0c;它主要是關于圖像&#xff0c;位置&#xff0c;存儲&#xff0c;多任務等功能的增加。 新增的元素有繪畫 canvas &#xff0c;用于媒介回放的 video 和 audio 元素…




閱讀更多...

















Error-Project facet Java version 1.8 is not supported








Error-Project facet Java version 1.8 is not supported




最近導入最新的Strtus2.5.10.1 Demo時出現了這個錯誤 解決方案如下&#xff1a; 選中工程——右鍵——Properties 然后依次展開找到如圖所示內容&#xff0c;將1.8改成1.7即可。 原因&#xff1a;工程默認配置是1.8&#xff0c;而本地環境JDK版本為1.7&#xff0c;兩則不匹配造…




閱讀更多...

















6.2








6.2




轉載于:https://www.cnblogs.com/tutuaixiaomei/p/3354356.html




閱讀更多...

















Tomcat全攻略








Tomcat全攻略




內容&#xff1a; 一&#xff1a;簡單介紹二&#xff1a;安裝及配置三&#xff1a;應用四&#xff1a;綜述參考資料關于作者宗 鋒西北大學計算機系碩士2001 年 12 月 隨著java的流行&#xff0c;其在web上的應用也越來越廣&#xff0c;tomcat作為一個開源的servlet容器&#xf…




閱讀更多...

















《G檔案》中關于游戲程序設計的文章








《G檔案》中關于游戲程序設計的文章




剛拿到前導的《G檔案》&#xff0c;發現了主程劉剛的文章&#xff0c;是目前我所見 到的關于游戲編程的最好的一篇&#xff0c;與大家共享。轉載&#xff1a;http://www.360doc.cn/article/2778_53476.html PC游戲編程 目錄 1 游戲程序理論 1.1  技術基礎 1.2  游戲底層 1.3  編…




閱讀更多...

















shell筆記








shell筆記




system 磁盤 磁盤空間使用情況df查看文件或目錄大小du掛載usb sudo fdisk -l  # Find what the drive is called e.g. /dev/sdb1
sudo mkdir /media/usb
sudo mount /dev/sdb1 /media/usb
sudo umount /media/usb# umount
sudo umount /media/usb utils awk 打印文件的第一列(域…




閱讀更多...

















html5編輯文檔,HTML5帶各種趣味動畫的文本編輯器








html5編輯文檔,HTML5帶各種趣味動畫的文本編輯器




CSS語言&#xff1a;CSSSCSS確定body {background-color: #eee;}html,body {margin: 0px;height: 100%;overflow: hidden;}.toolbar {width: 100%;background: #fff;padding: 4px 10px;}.characters {display: inline-block;margin-right: 20px;vertical-align: top;}.characte…




閱讀更多...

















社會轉型








社會轉型




轉載&#xff0c;版權由作者所有。 常常在政府工作報告中看到關于“社會轉型期”的說法&#xff0c;不是太明白&#xff0c;在百度里找了找&#xff0c;果然有不少&#xff0c;摘抄下來&#xff0c;做為學習資料用&#xff1a; 一是指體制轉型&#xff0c;即從計劃經濟體制向市…




閱讀更多...

















在WPF中處理Windows消息








在WPF中處理Windows消息




在Winform中 處理Windows消息通過重寫WndProc方法 在WPF中 使用的是System.Windows. Sytem.Windows.Controls等名字空間&#xff0c;沒有WndProc函數 WPF中處理消息首先要獲取窗口句柄&#xff0c;創建HwndSource對象 通過HwndSource對象添加消息處理回調函數。 此外 WPF中沒有…




閱讀更多...

















Android Material風格的應用(三)--DrawerLayout








Android Material風格的應用(三)--DrawerLayout




添加抽屜導航 Android Material風格的應用(一)--AppBar TabLayoutAndroid Material風格的應用(二)--RecyclerViewAndroid Material風格的應用(三)--DrawerLayoutAndroid Material風格的應用(四)--FloatActionButtonAndroid Material風格的應用(五)--CollapsingToolbar DrawerLa…




閱讀更多...

















html5 數據緩存,HTML5: 本地緩存








html5 數據緩存,HTML5: 本地緩存




HTML5 提供了兩種在客戶端存儲數據的新對象&#xff1a;localStorage&#xff1a;沒有時間限制的數據存儲&#xff0c;在同一個瀏覽器中&#xff0c;只要沒被手動清理&#xff0c;第二天、第二周或下一年之后&#xff0c;數據依然可用。sessionStorage&#xff1a;針對一個 ses…




閱讀更多...


















最新文章


















Copyright @ 2022~2023