c++ 全排列算法

1.对于无重复值的情况
*
* 固定第一个字符，递归取得首位后面的各种字符串组合；
* 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； *递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
*
2.假如有重复值呢？
*由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。
* 例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。
* 但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。
* 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。
*
* 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，
* 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！

最简单的：

class Solution { 
    public: vector<string> Permutation(string str) { 
    vector<string> result; int i = 0; if (str.empty()) { 
    return result; } permution(str,i,result); sort(result.begin(), result.end()); vector<string>::iterator it; for (it = result.begin(); (it+1) != result.end();) { 
    if (*it == *(it + 1)) { 
    it = result.erase(it); } else it++; } return result; } void permution(string str, int i, vector<string>& result) { 
    if (i==str.length()-1) { 
    result.push_back(str); } for (int j = i; j < str.length();j++) { 
    char temp = str[i]; str[i] = str[j]; str[j] = temp; permution(str, i + 1, result); temp = str[i]; str[i] = str[j]; str[j] = temp; } } }; 

改进一下：

public ArrayList<String> Permutation(String str){ 
    ArrayList<String> list = new ArrayList<String>(); if(str!=null && str.length()>0){ 
    PermutationHelper(str.toCharArray(),0,list); Collections.sort(list); } return list; } private void PermutationHelper(char[] chars,int i,ArrayList<String> list){ 
    if(i == chars.length-1){ 
    list.add(String.valueOf(chars)); }else{ 
    Set<Character> charSet = new HashSet<Character>(); for(int j=i;j<chars.length;++j){ 
    if(j==i || !charSet.contains(chars[j])){ 
    charSet.add(chars[j]); swap(chars,i,j); PermutationHelper(chars,i+1,list); swap(chars,j,i); } } } } private void swap(char[] cs,int i,int j){ 
    char temp = cs[i]; cs[i] = cs[j]; cs[j] = temp; } 

考虑字典算法：参考http://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html

public ArrayList<String> Permutation2(String str){ 
    ArrayList<String> list = new ArrayList<String>(); if(str==null || str.length()==0){ 
    return list; } char[] chars = str.toCharArray(); Arrays.sort(chars); list.add(String.valueOf(chars)); int len = chars.length; while(true){ 
    int lIndex = len-1; int rIndex; while(lIndex>=1 && chars[lIndex-1]>=chars[lIndex]){ 
    lIndex--; } if(lIndex == 0) break; rIndex = lIndex; while(rIndex<len && chars[rIndex]>chars[lIndex-1]){ 
    rIndex++; } swap(chars,lIndex-1,rIndex-1); reverse(chars,lIndex); list.add(String.valueOf(chars)); } return list; } private void reverse(char[] chars,int k){ 
    if(chars==null || chars.length<=k) return; int len = chars.length; for(int i=0;i<(len-k)/2;i++){ 
    int m = k+i; int n = len-1-i; if(m<=n){ 
    swap(chars,m,n); } } }