1、全排列
问题描述
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解题思路

基本思路是递归加回溯。
这个问题转化为从左到右n个空行，n个数，每个数每次都只能使用一次，依次放入到所有的不同的n个空行中，返回所有的可能排列结果，即为全排列。使用函数递归和回溯法来解决这个问题。
随着递归的深入，直到元素序列只剩下最后两个时，将其交换。递归回退到上一层。随着循环，将在该层递归的前提下，序列从左到右依次与该层递归中的序列第一个元素交换，每交换一次后，再次进入递归将这这种情况下的所有可能结果随着递归排列完毕。在以该层递归的所有情况排列完毕后，递归函数回退到再上一层，再进行漫长地以该层递归为首的元素与其后面的所有元素交换再递归。以此类推，直到整个序列中的第一个元素与所有元素交换完毕并依次完成所有全排列后，算法结束，全排列完成。
下图是LeetCode中的官方题解中的动态图。



代码实现
class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& nums, int index, int len){
        if (index == len) {
            res.push_back(nums);
            return;
        }
        for (int i = index; i < len; i++) {
            // 动态维护数组
            swap(nums[i], nums[index]);
            // 继续递归填下一个数
            backtrack(res, nums, index + 1, len);
            // 撤销操作
            swap(nums[i], nums[index]);
        }
    }
    vector< vector<int> > permute(vector<int>& nums) {
        vector< vector<int> > res;
        int len = nums.size();
        backtrack(res, nums, 0, len);
        return res;
    }
};
//他如果输入的是{1, 2, 3}的话，打印结果是：
/*
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
请按任意键继续. . .
*/

运行截图

在VS2013上的运行情况
#include<iostream>
#include<vector>
#include<algorithm>
using namesapce std;

void backtrack(vector< vector<int> > &res, vector<int> &nums, int index, int len){
	if (index == len){
		res.push_back(nums);
		return;
	}
	for (int i = index; i < len; i++){
		swap(nums[i], nums[index]);
		backtrack(res, nums, index + 1, len);
		swap(nums[i], nums[index]);
	}
}

vector< vector<int> > permute(vector<int>& nums){
	vector< vector<int> > res;
	int len = nums.size();
	backtrack(res, nums, 0, len);
	return res;
}

void main()
{
	vector< vector<int> > res;
	vector<int> nums = { 1, 2, 3, 4 };
	res = permute(nums);
	for (int i = 0; i < res.size(); i++){
		for (int j = 0; j < res[i].size(); j++){
			cout << res[i][j] << " ";
		}
		cout << endl;
	}
	system("pause");
	return;
}
/*
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
1 4 2 3
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
3 1 2 4
3 1 4 2
3 4 1 2
3 4 2 1
4 2 3 1
4 2 1 3
4 3 2 1
4 3 1 2
4 1 3 2
4 1 2 3
请按任意键继续. . .
*/

2、全排列 II
问题描述
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解题思路

两种思路，提交结果时间复杂度都差不多。分别是在存储结束后去重和在存储的过程中使用集合来去重。???

-思路改天再缕缕。

代码实现（1）
class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int> nums, int idx) {
        int n = nums.size();
        if (idx == n) 
        	ans.emplace_back(nums);

        unordered_set<int> s;
        for (int i = idx; i < n; ++i) {
            if (s.find(nums[i]) != s.end()) 
            	continue; //剪枝
            s.insert(nums[i]);

            vector<int> tmp = nums;
            swap(tmp[idx], tmp[i]);
            dfs(tmp, idx + 1);  
        }
    }
};

运行截图

代码实现（2）
class Solution {
public:

    void backtrack(vector< vector<int> >& res, vector<int> & nums, int index, int len){
        if(index == len){
            res.push_back(nums);
            return;
        }
        for(int i = index; i < len; i++){
            if((i + 1) != len and nums[i] == nums[i + 1])
                continue;
            swap(nums[i], nums[index]);
            backtrack(res, nums, index + 1, len);
            swap(nums[i], nums[index]);
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector< vector<int> > res;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        backtrack(res, nums, 0, len);
        sort(res.begin(), res.end());
        vector< vector<int> >::iterator iter = res.begin();
        iter = unique(res.begin(), res.end());
        vector< vector<int> > ans(res.begin(), iter);
        return ans;
    }
};

运行截图

3、第k个排列
问题描述
给出集合[1,2,3,…,n]，其所有元素共有n!种排列。
按大小顺序列出所有排列情况，并一一标记，当n = 3时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1,  n!]。

示例 1:
输入: n = 3, k = 3
输出: "213"

示例 2:
输入: n = 4, k = 9
输出: "2314"

解题思路

首先用vector容器存储1到n数字。
定义一个计算阶乘的函数，用于计算每位的阶乘数。
k值对n-1位的阶乘数取整，该整数就是第一位应该从vector中所取数字的下标。
将该作为下标的数字所对应的vector容器取出，存放到string容器中，将该数字从vector中移除。
(k-1)值对n-1位的阶乘数取余即为下一轮循环中的开始k值，每次循环n减1，直到n为0为止。
k-1是边界的一个处理，比如n=4,k=6时，输出的排列字符串应该是1开头的排列的最后一个，如果用k/(n-1)!的话，则会输出第一个字符为2，所以，统一使用(k-1)/(n-1)!。因为用的是闭区间[]，不减1的话边界统一不起来，会成为[)。

代码实现
class Solution {
public:
    int getnum(int n){ // 求阶乘函数
        int ans = 1;
        for(int i = 1; i <= n; i++)
            ans *= i;
        return ans;
    }
    string getPermutation(int n, int k) {
        vector<int> v;   
        for(int i = 1; i <= n; i++)   
            v.push_back(i);
        string ans;
        while(n){
            int t = (k - 1) / getnum(n - 1);  
            ans += to_string(v[t]);
            v.erase(v.begin() + t);
            k -= (t * getnum(n - 1));
            n--;
        }
        return ans;
    }

};

运行截图

4、下一个排列
问题描述
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解题思路

这种全排列的规则就是最开始是完全正序的，然后从右向左依次逐一去逆序，这也满足递归思想，后面的n个数全部为逆置序列说明穷举了所有排列可能，此时将倒数第n+1个数与后面的某一个进行交换，此时后面的n个数又将呈现为正序排列情况，以此类推，循环，直到序列中所有元素均为逆序。
所以，求第k个排列的下一个排列，就是从右向左找到第一个出现逆序的元素，用下标i来指向该元素，则说明i后面的素所有元素已经全部逆序，再次从右向左找到第一个大于等于nums[i]的元素，用下标j来指向，将其两两交换，nums[j]即为下一个需要跃进的元素。交换后，nums[j]后面的元素两端由右向左，由左向右，两两交换，即可把后面的逆序转化为正序。

代码实现
class Solution {
public:
    void reverse(vector<int>& nums, int start) {
        int i = start, j = nums.size() - 1;
        while (i < j) {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while(i >= 0 and nums[i + 1] <= nums[i])
            i--;
        if(i >= 0){
            int j = nums.size() - 1;
            while(j >= 0 and nums[j] <= nums[i])
                j--;
            swap(nums[i], nums[j]);
        }
        reverse(nums, i + 1);
    }
};

运行截图

题目

/**
 * LeetCode60 n个数的排列组合找出第k个排列
 * 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 k th permutation sequence.
 Note: Given n will be between 1 and 9 inclusive.

 时间限制：1秒
 */

分析

乍看是1~N这N个数字的全排列
变化是，每排好一个就计数，计数到k就输出当前排好的这个数
注意，如何控制数字按从小到大出现？在算法思维（递归）训练：输出字符串字符的全排列中无需考虑顺序，而且经过实验输出的数字并非完全按从小到大排列。所以需要微调swap函数
代码

public class PermutationSequence {

  int count;
  String result;

  public String getPermutation(int n, int k) {
    char[] arr = new char[n];
    for (int i = 0; i < n; i++)
      arr[i] = (char) ('1' + i);
    permutation(arr, 0, k);
    return result;
  }

  private void permutation(char[] arr, int index, int cc) {
    //至于什么时候输出，要考虑清楚
    //考虑：只有所有位置上的字符都确认即index到达末尾，才算是排好一种情况
    if (index == arr.length) {
      count++;
      // System.out.println(String.valueOf(arr));
      if (count == cc)
        result = String.valueOf(arr);
    }
    //现在index之前的字符都已就位，把之后的每个字符都交换到index这个位置
    for (int k = index; k < arr.length; k++) {
      //尝试交换
      swap1(arr, index, k);
      //交换之后index这个位置就定好了，接下来的事就是递归去解决index+1位置开始的全排列就好了
      permutation(arr, index + 1, cc);
      // 前面我们尝试交换，把全排列求出来了，交换时只尝试了一个字符，因此for循环继续之前要换回来，继续尝试交换下一个字符
      swap2(arr, index, k);
    }
  }

  private void swap1(char[] arr, int index, int k) {
    char tmp = arr[k];
    //用插入法不改变后续元素的大小顺序
    for (int i = k; i > index; i--) {
      arr[i] = arr[i - 1];
    }
    // arr[k] = arr[index];
    arr[index] = tmp;
  }

  private void swap2(char[] arr, int index, int k) {
    char tmp = arr[index];
    //用插入法不改变后续元素的大小顺序
    for (int i = index; i < k; i++) {
      arr[i] = arr[i + 1];
    }
    arr[k] = tmp;
  }

  public static void main(String[] args) {
    Instant now = Instant.now();
    //考虑极限情况消耗的时间：约19毫秒
    System.out.println(new PermutationSequence().getPermutation(9,362880));
    //结果应该是987654321，362880=9！
    System.out.println("毫秒："+(Instant.now().toEpochMilli()-now.toEpochMilli()));
  }
}

求n位数的第k个全排列

利用 n个数字的全排列为n！
我们从第一个开始选

假设n =3。k=5
"123"
"132"
"213"
"231"
"312"
"321"

我们要确定第一位数是什么。
我们知道2的阶乘是 2
即每次跨越2个。
所以（5-1）/2=2
即我们跨越了2个 2
则所选数字为 第3个可选数字（用vis去查找可选数字）

注意最后一个数字要单独去找。
class Solution {
public:
    string getPermutation(int n, int k) {
        int num[11], vis[11], i, j, index;
        memset(vis,0,sizeof(vis));
        num[0] = 1;
        for(i = 1;i <= 9; i++){
            num[i] = num[i-1] * i;
        }
        num[1] = 1;
        string ans;
        i = n-1;   
        while(i > 0){
            index = (k-1)/num[i];
            k = k - index * num[i]; 
            for(j = 1;j <= n;j++){
                if(!vis[j]){
                    if(index == 0)
                        break;
                    index--;    
                }
            }
            ans += j + '0';
            vis[j] = 1;
            i--;
        }
        
        for(j = 1;j <= n;j++)
          if(!vis[j])
                 break;
        ans += j + '0';        
        return ans;
    }
};

题目描述：
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 k thpermutation sequence.
Note: Given n will be between 1 and 9 inclusive.
思路解析：
先把1到n的每个数存入list中，然后后边写一个数字，就可以从里面删掉一个了。
n个数字有n!个排列方式，n-1就有(n-1)！个排列方式，
为了和下标保持一致，需要k--，k/（n-1）！是当前字符的下标（注意是从零开始啊，下标0对应的数字1）
下一次的k就可以更新为 k%(n-1)!，循环n次
需要一个times表示每次更新阶乘的除数。
代码：
import java.util.*;
public class Solution {
    public String getPermutation(int n, int k) {
        k--;
        List<Integer> list = new ArrayList<Integer>();//注意存储1-n
        StringBuilder s = new StringBuilder();
        int times = n-1;
        for(int i=1;i<=n;i++){
            list.add(i);
        }
        int factorail = 1;//阶乘
        for(int i=2;i<n;i++){//不要×n
            factorail*=i;
        }
        while(times>=0){
            int indexList = k/factorail;
            s.append(list.get(indexList));
            list.remove(indexList);
            k=k%factorail;
            if(times!=0){
                factorail/=times;
            }
            times--;
        }
        return s.toString();
    }
}