全排列算法

全排列算法详解：递归方法与非递归方法

全排列算法在计算机科学中有着广泛的应用，特别是在组合优化、图算法和密码学中。本文将详细介绍两种实现全排列的常用方法：递归方法和非递归（字典序）方法。

什么是全排列？

全排列指的是对一组元素的所有可能顺序进行重新排列。对于一个包含 n 个不同元素的集合，其全排列共有 n!（即 n 的阶乘）种可能。例如，集合 {1, 2, 3} 的全排列包括 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, 和 {3, 2, 1}。

递归方法

递归方法利用回溯技术生成所有可能的排列。每次将一个元素固定，然后对剩余元素进行递归排列。

代码实现

import java.util.ArrayList;
import java.util.List;
 
public class Permutations {
 
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), results);
        return results;
    }
 
    private static void backtrack(int[] nums, List<Integer> path, List<List<Integer>> results) {
        // 如果当前路径的长度等于数组长度，表示完成一个排列
        if (path.size() == nums.length) {
            results.add(new ArrayList<>(path));
            return;
        }
 
        for (int num : nums) {
            if (path.contains(num)) continue; // 忽略已在路径中的数字
            path.add(num); // 选择当前数字
            backtrack(nums, path, results); // 递归生成剩余的排列
            path.remove(path.size() - 1); // 撤销选择，回溯
        }
    }
 
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = permute(nums);
        for (List<Integer> permutation : permutations) {
            System.out.println(permutation);
        }
    }
}

代码解析

permute 方法：初始化结果列表并调用回溯方法。
backtrack 方法：
- 如果临时列表的大小等于数组长度，则将其添加到结果列表中。
- 否则，遍历数组，如果当前元素已经存在于临时列表中则跳过，否则将其添加到临时列表中并递归调用回溯方法，然后移除最后一个元素进行回溯。

非递归方法（字典序法）

字典序法生成全排列的非递归方法。每次找到当前排列的下一个排列，直到生成所有排列。

代码实现

import java.util.Arrays;
 
public class NextPermutation {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Arrays.sort(nums); // 确保初始排列是字典序最小的排列
        do {
            System.out.println(Arrays.toString(nums));
        } while (nextPermutation(nums));
    }
 
    public static boolean nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
 
        // 从后向前找到第一个降序元素 i
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
 
        if (i >= 0) {
            // 找到第一个大于 nums[i] 的元素 j，并交换 nums[i] 和 nums[j]
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
 
        // 反转 i + 1 到数组末尾的部分，使其成为最小字典序
        reverse(nums, i + 1, n - 1);
        return i >= 0;
    }
 
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
 
    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

代码解析

nextPermutation 方法：
- 从后向前找到第一个降序元素 i。
- 如果找到，找到第一个大于 nums[i] 的元素 j，并交换 nums[i] 和 nums[j]。
- 反转 i + 1 到数组末尾的部分，使其成为最小字典序。
- 返回是否存在下一个排列。
辅助函数：
- swap：交换数组中的两个元素。
- reverse：反转数组中的一段，使其顺序颠倒。

示例输出

执行上述代码后，将输出所有排列组合：

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

总结

本文介绍了两种生成全排列的方法：递归方法和非递归（字典序）方法。

递归法：通过递归和回溯来生成全排列，代码较为直观，但可能会有较多的递归调用，导致栈的深度增加。
字典序法：通过不断生成下一个字典序排列来实现全排列，避免了递归调用，适合于需要按顺序生成排列的情况。

这两种方法在生成全排列时各有优缺点，可以根据具体需求选择合适的方法。

337. 打家劫舍 III 排序算法