题目描述

给定一个数字列表，返回其所有可能的排列。（你可以假设没有重复数字）
例子：给出一个列表[1,2,3]，其全排列为：

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

思路

递归1（穷举法）

对于长度为n的数组，其全排列为：第n位的值与长度为n-1的全排列的组合。
考虑每次递归，选择一个未出现在List中的数组元素添加到队列，再向下递归，直到组成一种排列。
那怎么实现全排列呢？体现在添加元素要遍历数组，如果递归回退后，要在List里删除之前添加的元素，继续查找新的元素添加到List。

所以，每一次递归，遍历数组，在List里添加一个新元素a，再向下递归。递归返回后，在List里删除之前添加的元素a，再遍历a元素之后的元素，找到新元素并添加到List，继续向下递归。
递归返回后，不需要从头遍历数组，因为上一次添加到List的元素a前面的元素已经都试过了。

递归终止条件：

如果List的元素个数与数组个数相同，表示完成了一种组合，将该List添加到保存List的链表里，终止递归
如果遍历完了数组，则终止递归

递归2（交换法）

对于[1,2]，其全排序的方法为：1与1交换，与2的全排序。1与2交换，与1的全排序。
对于[1,2,3]，其全排序为：1与1交换，与[2,3]的全排序。1与2交换，与[1,3]的全排序。1与3交换，与[2,1]的全排序。

由此可知，求全排列，就是拿当前元素（这里为1）与包括其自身在内的后面的元素交换，与后面元素的全排列的组合（因此可采用递归）。
注意，在递归返回时，需要将之前交换的位置还原。例如[1,3,2]添加到List后，之前互换的3、2需要还原各自的位置回到[1,2,3]，不然会影响之后的递归，因为递归算法的条件是基于初始数组位置不变递归的。

非递归1（后继法）

把每一种排列当作一个数。例如对数组[1,2,3]，其全排列包含6!个数字，没毛病
所以如果能找到这6!个数，也就找到了全排列

首先将数组按升序排序
找每个数字的后继（比当前排序表示的值大的当中的最小的那个）
- 从最右开始遍历数组，找到极大值（设极大值的下标是max，满足num[max-1] < num[max]即可）
- 找到max右边（包含max）大于num[max-1]的数中的最小值，与num[max-1]交换
  
  其实只要找到第一个比num[max-1]小的数，其前面一个就是满足条件的数，因为max及其右边的数字都是降序的，不然不满足求极大值的条件！
- 从max位到数组最右边倒序排列，即找到了后继数
当找不到极大值max时，说明已经找到了所有的数，完成了全排列

以求243765为例，求其后继数：
找到极大值max=7，交换5和3，变成：245763，再倒叙排列从7开始到末尾的数字，即763变成367，所以后继数为：245367

非递归2（逆序数阶乘进制法）

什么是逆序数？
定义逆序数：比数字a大且位于a的右边的数字的个数。
为什么是右边呢？因为阶乘进制位于最左边的位认为是最高位

举个例子：对于[1,2,3,4,5]，其一种排列为：32451，那么其逆序数为：22100
什么是阶乘进制？
n进制大家都知道，是当前位的值 * n的位数次方之和。
阶乘进制就是：当前位的值乘以当前位数的阶乘之和，注意最低位的位数为0!

对于上面的逆序数22100，其阶乘进制表示的数为：2乘以4的阶乘与2乘以3的阶乘与1乘以2的阶乘之和
逆序数、阶乘进制的运用
对于n个不同元素的数组，全排列有n!种。
每种排列对应的逆序数转化成阶乘进制后，值的范围恰巧是0~n!-1，即每种排列对应的逆序数对应一个阶乘进制的值。
求全排列，也就转化成：
- 先求对于阶乘进制在0~n!-1的值对应的逆序数
- 再将逆序数还原成对应的排列
  求逆序数：对逆序数22100，其对应的阶乘进制的值为62，根据62求其逆序数的方法：
- 最高位：62 / 4！ = 2，次高位：（62%4！）/ 3！= 2 …
  求逆序数（对于22100）对应的排序：
- 最高位为2，可知其右边有两个数字比它大，所以该位置的值是第三大的数
- 求后面的数时，别忘了忽略之前已经排好的数

代码

递归1

private List<List<Integer>> listHolder;
	
    public List<List<Integer>> permute(int[] nums) {
        listHolder = new ArrayList<List<Integer>>();
		List<Integer> list = new ArrayList<>();
        fullPack(nums, list);
        return listHolder;
    }
    
	private void fullPack(int[] nums, List<Integer> list) {
		if(list.size() == nums.length) {
			Integer[] result = list.toArray(new Integer[list.size()]);
			List<Integer> listCopy = new ArrayList(Arrays.asList(result));
			listHolder.add(listCopy);
			return;
		}
		for(int i = 0; i < nums.length; i++) {
			if(!list.contains(nums[i])){
				list.add(nums[i]);
				fullPack(nums, list);
				list.remove(list.size()-1);
			}
		}
		return;
	}

递归2

private static List<List<Integer>> listHolder;
	
	public static List<List<Integer>> permute(int[] nums) {
		listHolder = new ArrayList<List<Integer>>();
		
		//转化为List
		List<Integer> list = new ArrayList<>();
		for(int num : nums) {
			list.add(num);
		}
		myPermute(0, list);
		return listHolder;
	}
	
	private static void myPermute(int start, List<Integer> nums) {
		if(start == nums.size()-1) {
			List<Integer> aList = new ArrayList<Integer>(nums);
			listHolder.add(aList);
			return;
		}
		
		for(int i = start; i < nums.size(); i++) {
			swap(nums, start, i);
			myPermute(start+1, nums);
			swap(nums, i, start);
		}
	}
	
	private static void swap(List<Integer> nums, int i, int j) {
		int tmp = nums.get(i);
		nums.set(i, nums.get(j));
		nums.set(j, tmp);
	}

考察点

递归
int[]数组转化为List
- List的泛型类型是Integer不是int，所以需要先把int[]转化为Integer，方法就是遍历复制
- 然后将Integer[]数组转为队列：
  new ArrayList<Integer>(Arrays.asList(integers))
链表转数组
Integer[] result = list.toArray(new Integer[list.size()]);