全排列问题

题目：
给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:输入: [1,2,3]

输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

递归解法：
如示例中的集合{1,2,3}，排列情况有3！=6中排列方法。其第一个元素有3种选择1,2,3，对于第一个元素为1的排列，其第二个元素有2种选择2，3；第一个元素为2的排列，第二个元素也有2种选择1，3；第一个元素为3的排列，第二个元素为1,2两种选择。

class Solution {

public:

    void swap(vector<int>& nums,int p,int q)
    {
        int tmp=nums[p];
        nums[p]=nums[q];
        nums[q]=tmp;        
    }
    void resove(vector<int> &nums,int n,vector<vector<int>> &result)
    {
        if(n==nums.size())
        {
            result.push_back(nums);
            return;
        }
        for(int i=n;i<nums.size();i++)
        {
            swap(nums,n,i);
            resove(nums,n+1,result);
            swap(nums,n,i);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        if(nums.size()<=0) return result;
        resove(nums,0,result);
        return result;
    }
};

字典序解法：
这里先给出算法思想，然后在举例说明：
a.对于排列s[1...n]，找到所有满足s[k]<s k+1 的k的最大
值，如果这样的k不存在，则说明当前排列已经是a的所有排列
中字典序最大者，所有排列输出完毕。
b.在s[k+1...n]中，寻找满足这样条件的元素l，使得在所有a[l]>a[k]
的元素中，s[l]取得最小值。也就是说s[l]>s[k]，但是小于所有其
它大于s[k]的元素。
c.交换s[l]与s[k].
d.对于s[k+1...n]，反转该区间内元素的顺序。也就是说s[k+1]与
s[n]交换，s[k+2]与s[n-1]交换，……，这样就得到了s[1...n]在
字典序中的下一个排列。
示例：s={1,2,3,4,5}开始排列
假设此时序列为：s= {1,3,5,4,2},
经过步骤a,找到k=1,s[k+1]=5;
经过步骤b，找到l=3,s[l]=4;
步骤c，交换则 s[k(1)]=4,s[l(3)]=3,集合s={1,4,5,3,2};
步骤d,翻转则s={1,4,2,3,5}；到此得到下一个排列。
注意：以上举例是特殊情况，此示例开始序列为从小到大的排列的最小排列，如果给出的序列不是最小排列的如{0，-1,1}，则得不出正确结果，因题目是无重复元素，则具体写代码时可以以下标作为排列目标，最后打印时在确定具体元素。具体代码如下:
代码：

class Solution {
public:
    //翻转元素
    void reverse(vector<int> &nums,int s,int e)
    {
        for(int i=s;i<e;i++,e--)
        {
            int tmp=nums[i];
            nums[i]=nums[e];
            nums[e]=tmp;
        }
    }
    //插入元素，用下标来找具体元素
    void pushelement(vector<int> &nums,vector<int> &Index,vector<vector<int>> &result)
    {
        vector<int> r;
        for(int i=0;i<Index.size();i++)
        {
            r.push_back(nums[Index[i]]);
        }
        result.push_back(r);
    }
    //无重复元素，则用下标代表集合，以防出现非有序的元素：如[0,-1,1]
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        if(nums.size()<=0) return result;
        vector<int> Index;
        for(int i=0;i<nums.size();i++)
        {
            Index.push_back(i);
        }
        pushelement(nums,Index,result);
        while(true)
        {
            //寻找最大k值，使得Index[k]<Index[k+1]
            int k=Index.size()-1;
            bool bexist=false;
            for(;k>0;k--)
            {
                if(Index[k]>Index[k-1])
                {
                    k-=1;
                    bexist=true;
                    break;
                }
            }
            if(bexist==false)
            {
                return result;
            }
            //寻找最小值l,使得Index[l]>Index[k];
            int l=k+1;
            int tmp=Index[k+1];
            for(int i=k+2;i<Index.size();i++)
            {
                if(Index[i]>Index[k] && Index[i]<tmp)
                {
                    l=i;
                    tmp=Index[l];
                }
            }
            //交换Index[k]与Index[l];
            tmp=Index[k];
            Index[k]=Index[l];
            Index[l]=tmp;
            //翻转元素
            reverse(Index,k+1,Index.size()-1);
            pushelement(nums,Index,result);
        }
        return result;
    }
};

题目：给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例：输入: [1,1,2]
输出:[ [1,1,2],[1,2,1], [2,1,1]]
思路和上述，无重复的排列相同，只是在最开始对数组进行了排序，得到最小排列，另外为了去重： if(Index[i]>Index[k] && Index[i]<tmp) 此处改为： if(Index[i]>Index[k] && Index[i]<=tmp)，就能保证得到非重复的元素，其实，无重复的排列也可添加上等号不影响结果，本例这样写只是为了示例。代码如下：

class Solution {
public:
    //翻转元素
    void reverse(vector<int> &nums,int s,int e)
    {
        for(int i=s;i<e;i++,e--)
        {
            int tmp=nums[i];
            nums[i]=nums[e];
            nums[e]=tmp;
        }
    }
    //无重复元素，则用下标代表集合，以防出现非有序的元素：如[0,-1,1]
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        if(nums.size()<=0) return result;
        //排序,得到最小排列
        sort(nums.begin(),nums.end());
        result.push_back(nums);
        while(true)
        {
            //寻找最大k值，使得nums[k]<nums[k+1]
            int k=nums.size()-1;
            bool bexist=false;
            for(;k>0;k--)
            {
                if(nums[k]>nums[k-1])
                {
                    k-=1;
                    bexist=true;
                    break;
                }
            }
            if(bexist==false)
            {
                return result;
            }
            //寻找最小值l,使得nums[l]>numa[k];
            int l=k+1;
            int tmp=nums[k+1];
            for(int i=k+2;i<nums.size();i++)
            {
                //此处去重，可与无重复数字的全排列作比较，观察条件设置
                if(nums[i]>nums[k] && nums[i]<=tmp)
                {
                    l=i;
                    tmp=nums[l];
                }
            }
            //交换nums[k]与nums[l];
            tmp=nums[k];
            nums[k]=nums[l];
            nums[l]=tmp;
            //翻转元素
            reverse(nums,k+1,nums.size()-1);
            result.push_back(nums);
        }
        return result;
    }
};