字符串排列(全排列)_字符串排列,给定一个字符串stringa

题目描述

编写一个方法，确定某字符串的所有排列组合。

给定一个string A和一个int n,代表字符串和其长度，请返回所有该字符串字符的排列，保证字符串长度小于等于11且字符串中字符均为大写英文字符，排列中的字符串按字典序从大到小排序。(不合并重复字符串)

测试样例：

"ABC"

返回：["CBA","CAB","BCA","BAC","ACB","ABC"]

Solution 1

//标志位法
class Permutation {
public:
    static bool cmp(const string str1,const string str2)
    {
        return str1>str2;
    }
    void permutation(vector<string>&ans,int index,vector<int>flag,string str,string temp)
    {
        temp+=str[index];
        flag[index]=1;
        for(int i=0;i<str.size();++i)
        {
            if(!flag[i])
           permutation(ans,i,flag,str,temp);
        }
        if(temp.size()==str.size()) ans.push_back(temp);
    }
    vector<string> getPermutation(string A) {
        vector<string>res;
        vector<int>state(A.size());
        fill(state.begin(),state.end(),0);
        string ch;
        for(int i=0;i<A.size();++i)
        {
            ch="";
            permutation(res,i,state,A,ch);
        }
        sort(res.begin(),res.end(),cmp);
        return res;
    }
};

Solution 2

//拆分法，可以将abcd拆分为a[bcd]、b[acd]、c[abd]、d[abc]，其中[]代表全排列
class Permutation {
public:
    void permutation(string str,vector<string>&ans,int cnt)
    {
        if(cnt==str.size()-1) ans.push_back(str);
        for(int i=cnt;i<str.size();++i)
        {
            swap(str[cnt],str[i]);
            permutation(str,ans,cnt+1);
            swap(str[cnt],str[i]);
        }
    }
    vector<string> getPermutation(string A) {
        vector<string>res;
        if(A.size()<=0) return res;
        permutation(A,res,0);
        sort(res.begin(),res.end(),greater<string>());
        return res;
    }
};

同样的算法可以应用于数组，见   全排列的不同方式（递归和STL算法）