劍指offer之字元串的全排列

1 問題

求字元串的全排列，比如字元串abc，它的全排列如下

abc, acb, bac, bca, cad, cba      

 2 思路

我們先固定第一個字元，這裡的第一個字元肯定是這個字元串裡面字元串的全子集（不包含重複），abc字元串，我們a和a交換，這裡也就是固定a字元的，然後我們隻需要求出後面bc字元的全排列，這個時候我們可以用遞歸，我們依然b和b進行交換，c和c進行交換，到了末尾我們遞歸就結束，記得return.我們可以得出bc全排列的一種既bc,然後我們b和c需要交換位置，變成了cb,然後我們b和b進行了一次交換，然後我們可以得到bc全排列的一種既cb,是以固定a字元，我們可以得到全排列字元串abc acb,是以依次類推，我們可以固定b字元和c字元求出是以字元串的全排列

3 代碼實作

c++版本

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
class Permutation{
private:
    void permutation(string str, int begin);
public:
    vector<string> permutation(string str);
    vector<string> result;
};
 
vector<string> Permutation::permutation(string str)
{
    if (str.length() == 0)
    {
    return result;
    }
    permutation(str, 0);
    sort(result.begin(), result.end());   
    return result;
}
 
void Permutation::permutation(string str, int begin)
{
    if (begin == str.length())
    {
    result.push_back(str);
    return;
    }
    for (int i = begin; i < str.length(); ++i)
    {
    if (i != begin && str[i] == str[begin])
            continue;
    //這裡開始交換第一個元素和後面的元素，也就是起到固定的作用
        swap(str[begin], str[i]);
    //遞歸後面的子字元串
        permutation(str, begin + 1);
    //交換了要記得還原
    swap(str[i], str[begin]);
   }
} 
 
int main()
{
    Permutation h;
    h.permutation("abc");
    vector<string> result = h.result;
    for(int i = 0; i < result.size(); ++i)
    {
        std::cout << result[i] << std::endl;    
    }
    return 0;
}      

c版本

#include <stdio.h>
 
void permutation(char *str);
void permutation_core(char *str, char *begin);
 
void permutation(char *str)
{
    if (str == NULL) 
    {
        printf("str is NULL\n");
        return;
    }
    permutation_core(str, str);
}
 
void permutation_core(char *str, char *begin)
{
   if (*begin == '\0')
   {
       printf("%s\n", str);
   }
   else
   {
        for (char *ch = begin; *ch != '\0'; ++ch)
        {
            char temp = *ch;
            *ch = *begin;
            *begin = temp;
            permutation_core(str, begin + 1);
            temp = *ch;
            *ch = *begin;
            *begin = temp; 
 
        }
   } 
}
int main()
{
    //這裡不能用char *str = "adc",因為我們需要交換字元串裡面的字元，需要操作棧記憶體
    char str[] = "abc";  
    permutation(str);
    return 0;
}      

這樣寫，如果有重複的字元就有問題，比如ada,我們優化如下，去掉重

#include <stdio.h>
#include <string.h>
 
void permutation(char *str);
void swap(char *str, int start, int end);
void permutation_core(char *str, int begin, int end);
 
void permutation(char *str)
{
    if (str == NULL) 
    {
        printf("str is NULL\n");
        return;
    }
    int len = strlen(str);
    printf("len is %d\n", len);
    permutation_core(str, 0, len);
}
 
void permutation_core(char *str, int begin, int end)
{
    if (begin == end)
    {
        printf("%s\n", str);
    }
    else
    {
        for (int i = begin; i < end; ++i) 
        {
            if (i != begin && str[i] == str[begin])
                continue;
            swap(str, i, begin);
            permutation_core(str, begin + 1, end);  
            swap(str, i, begin);
        }
        
    }
    
}
 
 
void swap(char str[], int start, int end)
{
        char ch = str[start];
        str[start] = str[end];
        str[end] =  ch;
}
 
int main()
{
    //這裡不能用char *str = "adc",因為我們需要交換字元串裡面的字元，需要操作棧記憶體
    char str[] = "abc";  
    permutation(str);
    return 0;
}      

4 運作結果

c++版本運作結果

abc
acb
bac
bca
cab
cba      

c版本運作結果

abc
acb
bac
bca
cba
cab