## 字符串的全排列 ### 題目描述 輸入一個字符串，打印出該字符串中字符的所有排列。 例如輸入字符串abc，則輸出由字符a、b、c 所能排列出來的所有字符串 abc、acb、bac、bca、cab 和 cba。 ### 分析與解法 #### 解法一、遞歸實現 從集合中依次選出每一個元素，作為排列的第一個元素，然后對剩余的元素進行全排列，如此遞歸處理，從而得到所有元素的全排列。以對字符串abc進行全排列為例，我們可以這么做：以abc為例 - 固定a，求后面bc的排列：abc，acb，求好后，a和b交換，得到bac - 固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到cba - 固定c，求后面ba的排列：cba，cab。 代碼可如下編寫所示： ```cpp void CalcAllPermutation(char* perm, int from, int to) { if (to <= 1) { return; } if (from == to) { for (int i = 0; i <= to; i++) cout << perm[i]; cout << endl; } else { for (int j = from; j <= to; j++) { swap(perm[j], perm[from]); CalcAllPermutation(perm, from + 1, to); swap(perm[j], perm[from]); } } } ``` #### 解法二、字典序排列 首先，咱們得清楚什么是字典序。根據維基百科的定義：給定兩個偏序集A和B,(a,b)和(a′,b′)屬于笛卡爾集 A × B，則字典序定義為 (a,b) ≤ (a′,b′) 當且僅當 a < a′ 或 (a = a′ 且 b ≤ b′)。 所以給定兩個字符串，逐個字符比較，那么先出現較小字符的那個串字典順序小，如果字符一直相等，較短的串字典順序小。例如：abc < abcd < abde < afab。 那有沒有這樣的算法，使得 - 起點： 字典序最小的排列, 1-n , 例如12345 - 終點： 字典序最大的排列，n-1, 例如54321 - 過程： 從當前排列生成字典序剛好比它大的下一個排列 答案是肯定的：有，即是STL中的next_permutation算法。 在了解next_permutation算法是怎么一個過程之前，咱們得先來分析下“下一個排列”的性質。 - 假定現有字符串(A)x(B)，它的下一個排列是：(A)y(B’)，其中A、B和B’是“字符串”(可能為空），x和y是“字符”，前綴相同，都是A，且一定有y > x。 - 那么，為使下一個排列字典順序盡可能小，必有： - A盡可能長 - y盡可能小 - B’里的字符按由小到大遞增排列 現在的問題是：找到x和y。怎么找到呢？咱們來看一個例子。 比如說，現在我們要找21543的下一個排列，我們可以從左至右逐個掃描每個數，看哪個能增大（至于如何判定能增大，是根據如果一個數右面有比它大的數存在，那么這個數就能增大），我們可以看到最后一個能增大的數是：x = 1。 而1應該增大到多少？1能增大到它右面比它大的那一系列數中最小的那個數，即：y = 3，故此時21543的下一個排列應該變為23xxx，顯然 xxx(對應之前的B’）應由小到大排，于是我們最終找到比“21543”大，但字典順序盡量小的23145，找到的23145剛好比21543大。 由這個例子可以得出next_permutation算法流程為： next_permutation算法 - 定義 - 升序：相鄰兩個位置ai < ai+1，ai 稱作該升序的首位 - 步驟（二找、一交換、一翻轉） - 找到排列中最后（最右）一個升序的首位位置i，x = ai - 找到排列中第i位右邊最后一個比ai 大的位置j，y = aj - 交換x，y - 把第(i+ 1)位到最后的部分翻轉 還是拿上面的21543舉例，那么，應用next_permutation算法的過程如下： - x = 1； - y = 3 - 1和3交換 - 得23541 - 翻轉541 - 得23145 23145即為所求的21543的下一個排列。參考實現代碼如下： ```cpp bool CalcAllPermutation(char* perm, int num){ int i; //①找到排列中最后（最右）一個升序的首位位置i，x = ai for (i = num - 2; (i >= 0) && (perm[i] >= perm[i + 1]); --i){ ; } // 已經找到所有排列 if (i < 0){ return false; } int k; //②找到排列中第i位右邊最后一個比ai 大的位置j，y = aj for (k = num - 1; (k > i) && (perm[k] <= perm[i]); --k){ ; } //③交換x，y swap(perm[i], perm[k]); //④把第(i+ 1)位到最后的部分翻轉 reverse(perm + i + 1, perm + num); return true; } ``` 然后在主函數里循環判斷和調用calcAllPermutation函數輸出全排列即可。 #### 解法總結 由于全排列總共有n!種排列情況，所以不論解法一中的遞歸方法，還是上述解法二的字典序排列方法，這兩種方法的時間復雜度都為O(n!)。 ### 類似問題 1、已知字符串里的字符是互不相同的，現在任意組合，比如ab，則輸出aa，ab，ba，bb，編程按照字典序輸出所有的組合。 分析：非簡單的全排列問題（跟全排列的形式不同,abc全排列的話，只有6個不同的輸出）。 本題可用遞歸的思想，設置一個變量表示已輸出的個數，然后當個數達到字符串長度時，就輸出。 ```c //copyright@ 一直很安靜 && World Gao //假設str已經有序 void perm(char* result, char *str, int size, int resPos) { if(resPos == size) printf("%s\n", result); else { for(int i = 0; i < size; ++i) { result[resPos] = str[i]; perm(result, str, size, resPos + 1); } } } ``` 2、如果不是求字符的所有排列，而是求字符的所有組合，應該怎么辦呢？當輸入的字符串中含有相同的字符串時，相同的字符交換位置是不同的排列，但是同一個組合。舉個例子，如果輸入abc，它的組合有a、b、c、ab、ac、bc、abc。 3、寫一個程序，打印出以下的序列。 (a),(b),(c),(d),(e)........(z) (a,b),(a,c),(a,d),(a,e)......(a,z),(b,c),(b,d).....(b,z),(c,d).....(y,z) (a,b,c),(a,b,d)....(a,b,z),(a,c,d)....(x,y,z) .... (a,b,c,d,.....x,y,z)