全排列算法

全排列

一、数组中无重复元素

全排列的意思是对于一个给定的无重复元素的集合｛a1,a2,a3,a4……..an｝，求出它的所有的排序方式，这个问题其实可以用分治算法的思想来解决，首先可以把问题进行简化，例如：将一个字符串分为头部和尾部，其中头部是一个元素，尾部是剩下的所有元素，如下所示：

a bcd
b acd
c abd
d abc

此时上述的4个字符串已经包括了所有的在字符串的0索引这个位置可能出现的字符，但是要求的是整个字符串的排列，其实可以看成两步：第一步找出所有的可能出现在第一个位置的字符，然后交换它的第一个位置的字符，这个操作做完之后，其实第一个位置所有可能的情况都已经包括了，所以就固定不动第一个字符了，第二步按照同样的办法求每个字符串后面的所有字符的排列，方法依然是一样的，将后面字符依然分为头部和尾部，其中头部一个字符，尾部为所有剩下的字符，然后逐一将第一个字符与它后面的字符进行交换，直到最后只剩下一个字符，没法分为头部和尾部代表交换结束，此时也已经得到了所有的排列。

    abc
abc bac cba

acb abc bca bac cab cba

#code

void digui(string str,int begin,int l,vector<string> &res)
       {
           if(begin==l)
               res.push_back(str);
           else
           {
               for(int i=begin;i<=l;i++)
               {
                   swap(str[begin],str[i]);
                   digui(str,begin+1,l,res);
                   swap(str[begin],str[i]);
               }
           }
           return ;
       }
       vector<string> Permutation(string str) {
           vector<string> res;
           if(str.size()==0)
               return res;
           int l=str.size()-1;
           digui(str,0,l,res);
           return res;        
       }
   };

二、数组中有重复元素

当数组中存在重复的元素，那么就不能再和之前一样的，因为假设a1=a4，那么当a1和a4进行交换之后，字符串并没有任何变化，所以加上一行判断是否相等的代码就可以了。

#code

 class Solution {
public:
    void digui(string str,int begin,int l,vector<string> &res)
    {
        if(begin==l)
            res.push_back(str);
        else
        {
            for(int i=begin;i<=l;i++)
            {
                if(begin!=i&&str[begin]==str[i])//防止有相同的字符，就不用进行交换了，前面个判断条件是因为自身也需要交换一次，如果不加，就会一起跳过，就本来的排列都不会被添加进结果。。
                    continue;
                swap(str[begin],str[i]);
                digui(str,begin+1,l,res);
                swap(str[begin],str[i]);
            }
        }
        return ;
    }
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.size()==0)
            return res;
        int l=str.size()-1;
        digui(str,0,l,res);
        return res;        
    }
};