算法：15.全排列

https://www.lintcode.com/problem/permutations/description

描述

给定一个数字列表，返回其所有可能的排列。

你可以假设没有重复数字。

样例

给出一个列表，其全排列为：

挑战

使用递归和非递归分别解决。

思路递归算法就是解决一个问题时，可以先解决一个更小规模的问题（递归前进），然后根绝小规模问题的结果计算得出更大规模问题的结果（递归返回），当问题小到一定规模的情况下就不需要再分了，可以直接求解（递归边界）。排列的定义是从N个数中取出M个数按照一定顺序摆放成一行，就叫做N个数的一个M个数的排列，当两个排列的顺序与数字都相同时，视为同一个排列。例如：从【3，2，1】三个数中取出两个数的排列有【3，2】，【3，1】，【2，1】，【1，2】，【1，3】，【2，3】共六个排列。从【3，2，2】三个数中取出两个数的排列有【3，2】，【2，2】，【2，3】共三个排列，第一个数字取3，第二个数字不管是取第一个2还是第二个2，排列的结果都是【3，2】，视为同一个排列。全排列定义是从N个数中取出N个数的排列的集合称为全排列。递归的方法解决，N个数字的全部排列列表就是 [[一个数的排列],[两个数的排列],...[M个数的排列],...[N个数的排列]]。对于M个数字的排列，就是先求出 M-1 个数的排列集合，然后对于集合中的每个排列，如果排列的长度是length，那么将第M个数插入到排列中的第0,1,...j,...length 的位置上形成M个数的全部排列。

当数字列表是【1，2，3】时的求解过程。

当N等于1的时候，数字列表是【1】，返回的排列列表是 [ [1] ]。

当N等于2的时候，数字列表是【1，2】，遍历N等于1时返回的列表 [ [1] ]，由于列表中只有一个排列 [1]，长度是1，那么将第二个数字2插入到 [1] 的0，1位置形成新的排列 [2,1], [1,2]。那么当N等于2时的全排列就是 [ [2,1],[1,2] ]。

当N等于3的时候，就是将第三个数字3插入到 [[2,1],[1,2]] 中的每个排列的相应位置，最后的排列列表就是 [[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]]。

递归实现如下：

优化调整一下，删除复制数组：

非递归版本：

非递归版本的思路与递归版本是不同的。非递归版本的思路是，先列出第一个排列，然后通过交换已有排列中数字的位置来产生新的排列。

例如数字列表是 [1,2,3,4]，那么第一个排列就是原始的顺序，将 [1, 2, 3, 4] 作为第一个排列。然后从倒数第二个数字开始，也就是从3开始，将这个数字从当前的位置挪到最后，没挪动一个位置就产生一个排列。

初始的排列是 ：

[ [1, 2, 3, 4] ]

挪动3产生的排列是：

[1, 2, 4, 3]

3是倒数第二个数字，往后只能挪动一个位置，所以只产生一个新的排列。那么现在新的排列列表就是

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

挪动倒数第三个数字产生的新的排列是：

[1, 3, 2, 4] , [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2] 。

这是后得到的全部的排列就是：

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

其实质思想就是从后往前遍历各个数字。每次得到的全部排列，其最后面的m个个数字是m个数的一个全排列，然后将nums.length-m-1位置的数字插入到后面m个数字全排列的各个位置上形成新的m+1个数字的全排列。

第一次得到的排列列表是[ [1, 2, 3, 4] ] ，后面的 4 就是4的，全排列。

第二次得到的排列列表是 [ [1, 2,3, 4], [1, 2,4, 3]] ,所有排列的后两位组合起来就是后面两个数字 3 和 4 的一个全排列。

第三次得到的排列列表是 [[1,2, 3, 4], [1,2, 4, 3], [1,3, 2, 4], [1,3, 4, 2], [1,4, 2, 3], [1,4, 3, 2]]，所有排列的后三位组合起来就是最后三个数2，3，4的一个全排列。

小结

非递归操作在列表的操作中使用了 remove操作，对于ArrayList来说，remove会产生数组拷贝操作，效率较低。

实际中测试了使用LinkedList，对于输入 [1,2,3,4,5,6,7,8,9] 来说，ArrayList依然表现的比LinkedList要快，可能是数据量还是太小吧。