# 排列 字符串“abc”的全排列： abc? acb bac bca cba cab 求整個字符串的排列，可以分為兩步： 第一步，求所有可能出現在第一個位置的字符，即把第一個字符和后面所有的字符交換。第二步，固定第一個字符，求后面所有字符的全排列。這個時候仍然把后面所有字符分為兩部分：第一個字符以及其后所有字符。這是一個典型的遞歸問題。 例如字符串“abc”的全排列：以a開頭的全排列是a{bc}，遞歸得到bc的全排列，而bc的全排列又是以b開頭，c的全排列（即c自己）； ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?同樣，以b開頭的全排列是b{ac}，遞歸得到ac的全排列，而ab的全排列又是以a開頭，c的全排列。…… [http://blog.csdn.net/cinderella_niu/article/details/42930281](http://blog.csdn.net/cinderella_niu/article/details/42930281) ### 無重復的全排列 ?遞歸方法 如下是遞歸算法： ~~~ //全排列 void swap(int &a, int &b) { int temp = a; a = b; b = temp; } void Permutation(char str[], int index, int size) { cout << "Permutation(" << index << ", " << size << ")" << endl; if (index == size - 1) { //cout << "全排列："; //cout << str << endl;由于是全排列，還可以用這句打印結果 for (int i = 0; i < size; i++) cout << str[i]; cout << endl; } else { for (int i = index; i < size; i++) { //cout << "\t" << str; swap(str[index], str[i]); //cout << " swap(" << index << ","<< i << ") " << str << endl; Permutation(str, index + 1, size); //cout << "---\t" << str; swap(str[index], str[i]); //cout << " swap(" << index << ","<< i << ") " << str << endl << endl; } } } ~~~ ~~~ int main() { char test[] = "abc"; Permutation(0, sizeof(test) - 1); } ~~~ 下圖分別是運行注釋內語句和去掉注釋內語句的運行結果：  ? ? ? ? ? ? ? ? ?? 另一種寫法： ~~~ 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); } } } ~~~ ### 有重復的全排列 ?遞歸方法 由于全排列就是從第一個數字起每個數分別與它后面的數字交換。我們先嘗試加個這樣的判斷——如果一個數與后面的數字相同那么這二個數就不交換了。如abb，第一個數與后面交換得bab、bba。然后abb中第二數就不用與第三個數交換了，但對bab，它第二個數與第三個數是不相同的，交換之后得到bba。與由abb中第一個數與第三個數交換所得的bba重復了。所以這個方法不行。 *換種思維*，對abb，第一個數a與第二個數b交換得到bab，然后考慮第一個數a與第三個數b交換，此時由于第三個數等于第二個數，所以第一個數不再與第三個數交換。再考慮bab，它的第二個數與第三個數交換可以得到解決bba。此時全排列生成完畢。 這樣我們也得到了在全排列中去掉重復的規則——去重的全排列就是從第一個數字起每個數分別與它后面非重復出現的數字交換。用編程的話描述就是第i個數與第j個數交換時，要求[i,j)中沒有與第j個數相等的數。 ~~~ void swap(int &a, int &b) { int temp = a; a = b; b = temp; } ~~~ ~~~ //在pszStr數組中，[nBegin,nEnd)中是否有數字與下標為nEnd的數字相等 bool IsSwap(char *pszStr, int nBegin, int nEnd) { for (int i = nBegin; i < nEnd; i++) if (pszStr[i] == pszStr[nEnd]) return false; return true; } //k表示當前選取到第幾個數,m表示共有多少數. void PermutationHaveSameword(char *pszStr, int k, int m) { if (k == m) { static int s_i = 1; printf(" 第%3d個排列\t%s\n", s_i++, pszStr); } else { for (int i = k; i <= m; i++) //第i個數分別與它后面的數字交換就能得到新的排列 { if (IsSwap(pszStr, k, i)) { swap(pszStr[k], pszStr[i]); PermutationHaveSameword(pszStr, k + 1, m); swap(pszStr[k], pszStr[i]); } } } } ~~~ ~~~ int main(void) { char str[] = "aba"; PermutationHaveSameword(str, 0, sizeof(str) - 2); //Combination(str); //Permutation(str, 0, sizeof(str) - 1); return 0; } ~~~  ### 排列的非遞歸實習 這個木有懂，參考[http://blog.csdn.net/MoreWindows/article/details/7370155#t2](http://blog.csdn.net/MoreWindows/article/details/7370155) 至此我們已經運用了遞歸與非遞歸的方法解決了全排列問題，總結一下就是： 1．全排列就是從第一個數字起每個數分別與它后面的數字交換。 2．去重的全排列就是從第一個數字起每個數分別與它后面非重復出現的數字交換。 3．全排列的非遞歸就是由后向前找替換數和替換點，然后由后向前找第一個比替換數大的數與替換數交換，最后顛倒替換點后的所有數據。 ### 全排列的變形：部分排列 問題：從0-9這十個數字中選取3個數字進行排列，打印所有的組合結果。 這個問題就是全排列的變種了，全排列是求出了所有字母的排列方式，該題是求出了部分字母排列的方法。只需要將本文第一個程序“無重復的全排列 遞歸方法”中，程序結束的條件由if (index == size - 1)改為 if (index == m)即可，其中m是指要進行全排列的字符個數，比如m = 3。 ~~~ //全排列 void swap(int &a, int &b) { int temp = a; a = b; b = temp; } //從size個字符中選取m個字符進行全排列，打印排列結果 void Permutation(char str[], int index, int m, int size) { if (index == m) { //和本文第一個程序比只是這里打印時不太相同 for (int i = 0; i < m; i++) cout << str[i]; cout << "\t"; } else { for (int i = index; i < size; i++) { swap(str[index], str[i]); Permutation(str, index + 1, size); swap(str[index], str[i]); } } } ~~~ 測試從0-9中選兩個數的排列結果： ~~~ int main() { char test[] = "0123456789"; Permutation(test, 0, 2, sizeof(test) - 1); } ~~~  # 組合問題 題目：輸入一個字符串，輸出該字符串中字符的所有組合。舉個例子，如果輸入abc，它的組合有a、b、c、ab、ac、bc、abc。 長度為n的字符串，能構成長度為1的組合、長度為2的組合、……、長度為n的組合。假設我們想在長度為n的字符串中求m個字符的組合。我們先從頭掃描字符串的第一個字符。針對第一個字符，我們有兩種選擇：第一是把這個字符放到組合中去，接下來我們需要在剩下的n-1個字符中選取m-1個字符；第二是不把這個字符放到組合中去，接下來我們需要在剩下的n-1個字符中選擇m個字符。這兩種選擇都很容易用遞歸實現。 ~~~ 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); } //使用vector容器來存放要放入組合的字符 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); cout << *string << endl; Combination(string + 1 , number - 1 , result); result.pop_back(); Combination(string + 1 , number , result); } ~~~  ### 使用位運算求組合問題 一個長度為n的字符串，它的組合有2^n-1中情況，我們用1 ~ 2^n-1的二進制來表示，每種情況下輸出當前位等于1的字符。  ~~~ void Combination(char *str) { int len=strlen(str); for(int cur=1; cur < (1<<len); cur++) //遍歷所有的情況，1<<len就等于2^len，遍歷1 ~ 2^len-1 { for(int j=0; j < len; j++) //遍歷所有的字符 { if(cur & (1 << j)) //判斷哪一位為1，即輸出該位 cout << str[j]; } cout << endl; //一種情況結束 } } ~~~ # 八皇后問題 八皇后問題：[](http://zhedahht.blog.163.com/blog/static/2541117420114331616329/) ### [程序員面試題精選100題(58)-八皇后問題[算法]?](http://zhedahht.blog.163.com/blog/static/2541117420114331616329/ "閱讀全文") # [經典回溯算法（八皇后問題）](http://www.cnblogs.com/gaoteng/archive/2012/04/11/2442692.html) 參考：[http://blog.sina.com.cn/s/blog_6fb300a30100mvzp.html](http://blog.sina.com.cn/s/blog_6fb300a30100mvzp.html) ? ? ? ? ??[http://dongxicheng.org/structure/permutation-combination/](http://dongxicheng.org/structure/permutation-combination/) ? ? ? ? ??[http://blog.csdn.net/hackbuteer1/article/details/7462447](http://blog.csdn.net/hackbuteer1/article/details/7462447) ? ? ? ? ??[http://www.it165.net/pro/html/201412/28579.html](http://www.it165.net/pro/html/201412/28579.html)? ### ? ? ? ??[程序員面試題精選100題(59)-字符串的組合[算法]?](http://zhedahht.blog.163.com/blog/static/2541117420114172812217/ "閱讀全文")