字元串的全排列詳解

字元串的全排列

例如：輸入字元串abc，則輸出由字元a，b，c所能排列出來的所有字元串abc，acb，bac，bca，cab和cba

解析：典型的遞歸思路

step1：求出所有可能出現在第一個位置的字元。

step2：固定第一個字元，求後面所有字元的全排列

代碼：如下

其中：pStr指向整個字元串的第一個字元，pBegin指向目前做全排列操作的字元串第一個字元

void Permutation(char* pStr, char* pBegin)
 {
     if(*pBegin == '\0')
     {
         printf("%s\n", pStr);
     }
     else
     {
         //step1
         for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
         {
                 char temp = *pCh;//字母交換
                 *pCh = *pBegin;
                 *pBegin = temp; 

                 //step2   
                 Permutation(pStr, pBegin + );

                 temp = *pCh;//字母換回
                 *pCh = *pBegin;
                 *pBegin = temp;
         }
     }
 }
 void CallPermutation(char* pStr)
 {
     if(pStr == NULL)
         return;    
     Permutation(pStr, pStr);
 }
           

以上代碼是劍指offer上給出的代碼

問題

不難發現這個代碼存在問題，就是如果給定字元串存在重複字元，得到的結果就會出現重複

例如：測試以上代碼輸入：abb

則輸出結果将會是 :

abb

abb

bab

bab

bba

bba

然而這并不是我們期望的結果，面臨的一個問題就是：如何去重複？

問題解決：

分析：

全排列的實質就是就是從第一個字元起每個字元分别與它後面的字元交換，倘若沒有重複，則沒有問題。如果有重複，就會出現多餘的比較，進而出現多餘的排列結果。所有，自然會想到：去重的全排列就是從第一個字元起每個字元分别與它後面非重複出現的字元交換，例如：

對abb，第一個數a與第二個數b交換得到bab，然後考慮第一個數與第三個數交換，此時由于第三個數等于第二個數，是以第一個數就不再用與第三個數交換了。再考慮bab，它的第二個數與第三個數交換可以解決bba。

于是需要一個寫一個判重複的函數，如下

bool is_swap(char* begin, char* k)
 {   ///判斷是否需要交換

     for (; begin != k; begin++) {
         if (*begin==*k) {
             return false;

         }
     }    
     return true;
 }
           

給原函數加上判重複，代碼如下：

void Permutation(char* pStr, char* pBegin)
 {
     if(*pBegin == '\0')
     {
         printf("%s\n", pStr);
     }
     else
     {
         for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
         {
             if(is_swap(pBegin,pCh))
             {
                 char temp = *pCh;//字母交換
                 *pCh = *pBegin;
                 *pBegin = temp;    
                 Permutation(pStr, pBegin + );    
                 temp = *pCh;//字母換回
                 *pCh = *pBegin;
                 *pBegin = temp;
             }
         }
     }
 }
 void CallPermutation(char* pStr)
 {
     if(pStr == NULL)
         return;    
     Permutation(pStr, pStr);
 }
           

緻讀者：歡迎提出寶貴意見及建議，共同成長，共同進步！！！