D8 全排列(非回溯法)

全排列原题链接

在刷leetcode的时候，看到这道题目并没法使用像STL的next_permutation方法，感叹C++便利的同时，又惋惜Java并没有类似的API，那我们只能从原理入手了，仿写此算法。

其实回溯法更应该掌握，因为扩展性高，我们学知识本来就是举一反三的，如果这个算法只适用于这道题，那我们深入学习的必要性就没那么大了。

我们来看实现过程：

1. 找到「下降点」`i`

从右向左扫描数组，找到第一个 arr[i] < arr[i+1] 的位置 i。
为什么要找这个？因为字典序的排列从右向左最长的非递增序列是当前排列的尾部，我们想找到可以“升高”的那个位置。

说人话就是，这里非递增序列我们先理解为递减序列（其实还包括前后相等），其实是找递减序列的入口，为什么呢？

因为按照字典序来看，这一部分是不便于排列的，因为难以升高，我们得优先换这部分的前一部分。

如果还是不理解，可以继续往后看，看到后面就会明白这里为什么找下降点。

举例：
arr = [1, 3, 5, 4, 2]
从右往左，观察 arr[i] >= arr[i+1]：

4 >= 2 → 是
5 >= 4 → 是
3 >= 5 → 否，3 < 5
所以 i = 1（对应数字 3）。
如果 i < 0，说明整个数组是非递增序列（即当前排列是最大字典序），没有下一个排列，函数返回 false。

2. 找到交换点 `j`

从右向左找到第一个 arr[j] > arr[i] 的位置。
在 arr[i] 后面的序列中找一个比 arr[i] 大的最小数字交换，使排列字典序刚好变大一点。

继续上例：
i=1，arr[i]=3
从右往左找第一个比 3 大的元素：

2 <= 3 不符合
4 > 3 符合，且是最右边的符合条件元素
所以 j = 3。

3. 交换 `arr[i]` 和 `arr[j]`

交换 3 和 4，变成：

[1, 4, 5, 3, 2]

4. 反转 `i+1` 位置到数组末尾的部分

将 i+1 到末尾的子数组反转（升序排列），保证新排列是字典序中「紧接着」的下一排列。

这里 i+1=2，子数组是 [5, 3, 2]，反转后是 [2, 3, 5]，数组变成：

[1, 4, 2, 3, 5]

这个就是字典序的下一个排列。

既然这样，那么我们需要实现两个函数swap和reverse

class Solution {public List<List<Integer>> permute(int[] nums) {Arrays.sort(nums); //这段代码用于判断List<List<Integer>> ans = new ArrayList<>();do{List<Integer> temp = new ArrayList<>();for (int num : nums) {temp.add(num);}ans.add(temp);}while(nextPermutation(nums));return ans;}private static boolean nextPermutation(int[] arr){int i = arr.length - 2;while(i >= 0 && arr[i] >= arr[i + 1]) i--; //找到下降点if(i < 0) return false;int j = arr.length - 1;while(arr[j] <= arr[i]) j--; //找出比下降点大的swap(arr, i, j);reverse(arr, i + 1, arr.length - 1);return true;}private static void swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}private static void reverse(int arr[], int l, int r){while(l < r) swap(arr, l++, r--);}
}