以前刚入行当CRUD boy的时候，我常去刷leetcode,每次遇到排列问题以及它的变种我就抓瞎了，然后搜索别人的实现方式我发现我都无法理解，甚至我还背过这类题的解法，可惜没啥用，过几天又忘记了，想不到时隔多年，我还是找到了一种适合我理解的实现方式。
我们初高中的时候，都学过排列，它的概念是这么说的：从 n 个不同的元素中取出m（1≤m≤n）个不同的元素，按照一定的顺序排成一列，这个过程就叫排列。当 m=n 这种特殊情况出现的时候，就是全排列（All Permutation）。如果选择出的这 m 个元素可以有重复的，这样的排列就是为重复排列（否则就是不重复排列。
如果有这样一道题：求 1,2,3,4,5五个数字的全排列，那么该如何实现呢？我们都知道答案是有120种(54321=120)。
很明显这这里我们会想到用递归来做,以下是我的心路历程：
permutation.png
我这里只列举了3个数字的，不过也差不多一样的意思。代码应该很容易写出来，递归而已! 先回顾下递归三要素
- 一个问题的解可以分解为几个子问题的解
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
- 存在递归终止条件
5个数字都参与了全排列则递归终止
所以代码如下:
public class Permutation {
public static int count = 0;
/**
* @param numbers 函数执行前,当前还未参与全排列的数字
* @param result 函数执行前,已经参与过全排列的数字以及顺序
*/
public static void allPermutation(ArrayList<Integer> numbers, ArrayList<Integer> result) {
// 所有数字都参与过了，则排列结束
if (numbers.isEmpty()) {
System.out.println(result);
count++;
return;
}
for (int i = 0; i < numbers.size(); i++) {
// 从剩下的未排列的数字中选择一个加入结果
ArrayList<Integer> newResult = (ArrayList<Integer>) result.clone();
newResult.add(numbers.get(i));
// 将以选择的数字从未排列的列表中移出
ArrayList<Integer> newNumbers = (ArrayList<Integer>) numbers.clone();
newNumbers.remove(i);
// 递归调用，对于剩余的数字继续生成排列
allPermutation(newNumbers, newResult);
}
}
public static void main(String[] args) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4);
numbers.add(5);
allPermutation(numbers, new ArrayList<>());
assert count == 120;
}
}
我认为这里最重要的思想是将数字分为了两堆,分别是未参与排列的数字(numbers)以及已经参与过全排列的数字以及顺序(result)。
万万没想到，CRUD boy也找到了属于自己解题的方式。
