題目描述

輸入一個字符串，打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c 所能排列出來的所有字符串a(chǎn)bc, acb, bac, bca, cab, cba。

?

題目分析

窮舉與遞歸

又是一個經(jīng)典問題，最容易想到的解決方法仍然是窮舉（我實在是太愛窮舉法了，每當被問到算法問題不知道如何解決的時候，總可以祭出窮舉大旗，從而多爭取3分鐘的思考時間）。窮舉雖好，但它大多數(shù)情況下都不是被需要的那個答案，是因為看起來代碼太Low不夠高大上嗎？

在這種情況下，窮舉法裹著貂皮大衣的親戚——遞歸就出現(xiàn)了。雖然空間復雜度和時間復雜度沒有任何改進，而且還增加了系統(tǒng)開銷（關于遞歸法的系統(tǒng)開銷不在這里討論，之后再找專門的時間闡述），但是就是因為長得好看（代碼看起來精煉），遞歸的B格兒就高了很多。

遞歸法對于這個題目同樣非常適用，基本思路就是固定一個字符，然后對剩余的字符做全排列……不贅述，請自己想。如果你也跟我一樣永遠想不明白遞歸，那就畫畫圖，寫寫代碼，debug一下，每天花3-4個小時，靜下心來仔細捉摸，總（ye）會（bu）想（hui）明白的。貼一段July和他伙伴們在《程序員編程藝術：面試和算法心得》中的代碼實現(xiàn)，供做噩夢時使用。p.s. 我已加了注釋

?

/** Permute full array of input string by general recusion* @ char* perm [in/out] The string need to do permutation* @ int from [in] The start position of the string* @ int to [in] The end position of the string*/ void CalcAllPermutation(char* perm, int from, int to) {if (to <= 1){return;}if (from == to){//all characters has been permutedfor (int i = 0; i <= to; i++)cout << perm[i];cout << endl;}else{// always select one character, then full array the left ones.for (int j = from; j <= to; j++){ swap(perm[j], perm[from]); //swap the selected character to the beginning of stringCalcAllPermutation(perm, from + 1, to); // Permute left characters in full array.swap(perm[j], perm[from]); //recovery the string to original one (swap the selected character back to its position.) }} }

?

?

?

?

字典序

這是一個比遞歸更有趣的答案，不知道算不算經(jīng)典解法，起碼開拓了思路，跟每一次接觸新鮮的算法一樣，仍然想了半天的時間，因此照例把思考過程更細致的記錄下來（雖然July和他伙伴們在《程序員編程藝術：面試和算法心得》中已經(jīng)說了很多），再加上一些小修改。

字典序，顧名思義，就是按照字典的順序進行排列。根據(jù)維基百科的定義：給定兩個偏序集A和B,(a,b)和(a′,b′)屬于笛卡爾集 A × B，則字典序定義為(a,b) ≤ (a′,b′) 當且僅當 a < a′ 或 (a = a′ 且 b ≤ b′)。所以給定兩個字符串，逐個字符比較，那么先出現(xiàn)較小字符的那個串字典順序小，如果字符一直相等，較短的串字典順序小。例如：abc < abcd < abde < afab。

總結一下，字典序排序其實就是同一組字符組成的一系列字符串，

????起點： 字典序最小的排列, 1~n , 例如12345
??? 終點： 字典序最大的排列，n~1, 例如54321
??? 過程： 從當前字符串排列生成字典序剛好比它大的下一個排列，比如12345的字典序下一個排列是12354

?

現(xiàn)在來進一步分析一下算法實現(xiàn)，其實對于字典序排列，關鍵點就是找到“下一個排列”。基本的查找方法

假定現(xiàn)有字符串(A)x(B)，它的下一個排列是：(A)y(B’)，其中A、B和B’是“字符串”(可能為空），x和y是“字符”，前綴相同，都是A，且一定有y > x。那么，為使下一個排列字典順序盡可能小，必有：

• A盡可能長 （A越長，那么B‘就越短，從而y所在的位越低，很明顯的同一個字符放在低位肯定比放在高位要小，比如：100<10< 1, abc<aac<aaa）
  
• y盡可能小 （同一個位置上，字符越小整個字符串的字典序越小，比如：131<121, acd<abc）
• B'里的字符按由小到大遞增排列 (小朋友都懂的道理不解釋)
  

現(xiàn)在的問題是如何找到“x”和“y”?

舉個例子，現(xiàn)在我們要找21543的下一個排列，我們可以從左至右逐個掃描每個數(shù)，看哪個能增大（至于如何判定能增大，是根據(jù)如果一個數(shù)右面有比它大的數(shù)存在，那么這個數(shù)就能增大），我們可以看到最后一個能增大的數(shù)是：x = 1。而1應該增大到多少？1能增大到它右面比它大的那一系列數(shù)中最小的那個數(shù)，即：y = 3，故此時21543的下一個排列應該變?yōu)?3xxx，顯然 xxx(對應之前的B’）應由小到大排，于是我們最終找到比“21543”大，但字典順序盡量小的23145，找到的23145剛好比21543大。

抽象概括一下上面的例子就是“二找、一交換、一翻轉”。

??? 一找：找到排列中最后（最右）一個升序的首位位置i，x = ai

??? 二找：找到排列中第i位右邊最后一個比ai 大的位置j，y = aj

??? 一交換：交換x，y

??? 一翻轉：把第(i+ 1)位到最后的部分翻轉

*升序：相鄰兩個位置ai < ai+1，ai 稱作該升序的首位

?找21543的下一個排列，套用“二找、一交換、一翻轉”就是

一找: 找到排列中最后（最右）一個升序的首位, x = 1

二找: 找到排列中1的右邊最后一個比1大的位置，y = 3

一交換：1和3交換，得23541

一翻轉：翻轉541，得23145

道理講完了，但是你真的懂了嗎？反正本人看到這里又看了算法之后，仍然懵懵懂懂（請原諒我的智商吧，其實我自己也挺著急的，媽媽已經(jīng)急哭，表示對我放棄治療了）。因此，下面的部分很重要。

首先來看第一找“找到排列中最后（最右）一個升序的首位位置i，x = ai”

這意味著什么？這意味著字符串在x之后所有字符都是降序排列的，如下圖。在找到x=1之前，543已經(jīng)達到了最大字典序，因此不可能通過改變543的順序得到更大的字符串。

那么為什么不是修改首位的“2”呢？還記得前面介紹的字符串(A)x(B)的下一個排列是(A)y(B’)的方法嗎？，A要盡可能長。對“1”進行操作正式保證了A盡可能長。

接下來，看一下第二找和一交換：“找到排列中第i位右邊最后一個比ai 大的位置j，y = aj”，“交換x，y”

說完了“A要盡可能長”，現(xiàn)在該說y要盡可能小了。為什么“第二找”和“一交換”之后，y就最小了呢？既然首位的“2”是不在范圍內的，而“1”（即x）是要被交換的，那么y只能來自“5”，“4”，'3“，因為543是降序排列的（注意，x可是找到的字符串中最后一個升序的首位喲），因此“5”，“4”，'3“中比”1“（即x）大的最小的字符就是y。于是y=3。交換x，y之后，即得到新的字符串(A)y(B')

此時的B'仍然不是我們最終需要的B'，因為它還不滿足最后一個條件B'里的字符按由小到大遞增排列。為了做到這一點，于是有了最后的“一翻轉”。那么為什么簡單的翻轉之后B'里的字符就按照由小到大的順序排列了呢？

我們在來回顧一下B和B‘的確定過程。首先，B是一個降序排列的字符串；然后我們在B中找到了比x小的最小的y（此處有些繞，自己寫幾個字符串就一目了然了），也就是說y的右側如果還有字符的話也一定比x小（因為B是降序），接下來交換x和y得到B'，因此B’也是降序的。對于一個降序的字符串來說，翻轉之后即為升序排列。于是我們得到了最終的(A)y(B')，即23145。

?

代碼實現(xiàn)

好了，該講的都講完了，現(xiàn)在看代碼

/** Find out the next (bigger) permutation of current string.* @ char* perm [in/out] String* @ int num [in] The length of string.*/ bool FindNextPermutation(char* perm, int num) {int i = 0;for(i = num - 2; (perm[i] >= perm[i+1]) && i >= 0; --i); // Find xif(i < 0){return false; // The input string is a single character }int j = 0;for(j = num - 1; (j > i) && perm[j] <= perm[i]; --j); // Find y swap(perm[i], perm[j]); // swap x and yreverse(perm + i + 1, perm + num); // reverse B'return true; }

?

這段代碼實現(xiàn)了從當前字符串生成字典序剛好比它大的下一個排列，但是如果我們拿到的字符串不是字典序最小的排列，該如何處理呢？

對原始字符串進行排序，將原始字符串轉換為字典序最小的排列后，再通過字典序排序進行全排列。這樣做的好處是實現(xiàn)簡單，缺點是要多做一次字符串排序。關于排序算法不在本文討論范圍，這里我直接使用了STL的sort函數(shù)

?

void CalcByDictionary(const string &str) {char* perm = const_cast<char*>(str.c_str());sort(perm, perm+str.size());cout<<str<<endl;while(true){if(!FindNextPermutation(perm, str.size())){break;}cout<<s<<endl;} }

?

?

?

?

?

題外話

最近一直在看July和他伙伴們的《程序員編程藝術：面試和算法心得》，收獲良多。在學習的過程中發(fā)現(xiàn)，雖然原書講解的很細致，但是真正理解仍然需要花費大量的思考和實踐。因此做了這個系列的文章，只是希望將自己的思考記錄下來，供以后查閱。

?

?

轉載于:https://www.cnblogs.com/chailinbo/p/9269210.html

總結

以上是生活随笔為你收集整理的字符串的全排列(字典序排列)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。