Permutation问题

46.Permutations
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

代码如下：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> rec;
        if(nums.size()<=0)
          return rec;
        dfs(nums,0,rec);
        return rec;
    }
    
    void dfs(vector<int>& nums,int start,vector<vector<int>>& rec)
    {
        if(start==nums.size())
        {
            rec.push_back(nums);
        }
        else
        {
            for(int i=start;i<nums.size();i++)
            {
                swap(nums[start],nums[i]);
                dfs(nums,start+1,rec);
                swap(nums[start],nums[i]);
            }
        }
    }
};

**47.Permutations II **
Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

代码如下：

class Solution {
public:
    set<vector<int>> mSet;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> rec;
        if(nums.size()<=0)
          return rec;
        sort(nums.begin(),nums.end());
        dfs(nums,0);
        for(auto a:mSet)
          rec.push_back(a);
        //return vector<vector<int>>(mSet.begin(),mSet.end());
        return rec;
    }
    
    void dfs(vector<int>& nums,int start)
    {
        if(start==nums.size())
        {
            mSet.insert(nums);
            //rec.push_back(nums);
        }
        else
        {
            for(int i=start;i<nums.size();i++)
            {
                //if(i!=start&&nums[i]==nums[i-1])
                //  continue;
                swap(nums[start],nums[i]);
                dfs(nums,start+1);
                swap(nums[start],nums[i]);
            }
        }
    }
};

**31.Next Permutation **
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

代码如下：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if(n<=0)
          return;
        int pivot = -1;  
        int i = n-1;
        for(;i>=1;i--)   //从右到左，先找出数组中非增序序列，找到这个序列最大值左边的一个数A
        {                //并找出该非递增序列中比A大的最少的值B，交换两个数的值，然后对该递增序列排序
            if(nums[i]>nums[i-1])
            {
                pivot = i-1;
                break;
            }
        }
        if(pivot>=0)
        for(int j=n-1;j>=0;j--)
        {
            if(nums[j]>nums[pivot])
            {
                int temp = nums[j];
                nums[j] = nums[pivot];
                nums[pivot] = temp;
                sort(nums.begin()+pivot+1,nums.end());  //牢牢记住特殊的规则
                return;
            }
            
        }
        else
        {
            sort(nums.begin(),nums.end());
        }
        return;
    }
};

**60. Permutation Sequence **
The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
代码如下：

class Solution {
public:
    string getPermutation(int n, int k) {
        string rec = "";
        vector<int> num(10,0);
        for(int i=0;i<n;i++)
        {
            num[i] = i + 1;
        }
        
        k--;
        for(int i=n;i>=1;i--)
        {
            int j = k/getFac(i-1); 
            k %= getFac(i-1);       //除去非目标数字为首的字符串所占的位数
            rec += to_string(num[j]);
            for(int k=j;k<n-1;k++)
            {
                num[k] = num[k+1];  //把可选数字左移
            }
        }
        return rec;
        
    }
    int getFac(int t)
    {
        int result=1;
        while(t>0)
        {
            result *= t;
            t--;
        }
        return result;
    }
};