字符串的全排列详解

字符串的全排列

例如：输入字符串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);
 }
           

致读者：欢迎提出宝贵意见及建议，共同成长，共同进步！！！