每日算法 — 使用java实现字典序全排列：回溯生成与字典序排列算法

字典序全排列是排列组合与回溯算法的经典问题。给定一个不含重复元素的字符序列，按字典序输出其所有排列。本文用Java实现两种经典解法：基于回溯的深度优先搜索（DFS）和基于字典序的迭代算法（Steinhaus–Johnson–Trotter算法的简化版），并分析两种方法的时间与空间特性。

问题分析

字典序（Lexicographical Order） 是指按照字母表顺序比较字符串大小的方式。对于排列问题，字典序要求排列按照从左到右逐位比较的方式有序输出。

以字符序列 [1, 2, 3] 为例，其6个全排列按字典序为：

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

对于 $n$ 个不同元素的序列，全排列的总数为 $n!$ 个。

算法核心思想

回溯法（DFS）

通过深度优先搜索逐位填充排列中的元素。核心思想：
1. 维护一个used数组标记哪些元素已被使用
2. 递归到第 $i$ 层时，从所有未使用的元素中选择一个填入位置 $i$
3. 当填满 $n$ 个位置时得到一个完整排列
4. 回溯时释放占用的元素标记

为保证字典序，在每一层选择元素时按从小到大的顺序尝试。

字典序迭代法（C++ STL next_permutation原理）

该算法可以直接生成当前排列的下一个字典序排列，无需递归：

1. 从右向左找到第一个升序对：找到最大的索引 $i$ 使得 $a[i] < a[i+1]$。如果不存在这样的 $i$，说明已是最后一个排列
2. 从右向左找替换元素：找到最大的索引 $j$ 使得 $a[j] > a[i]$
3. 交换 $a[i]$ 和 $a[j]$
4. 反转 $a[i+1..n-1]$：将后缀变为升序（即最小排列）

Java完整实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 字典序全排列生成器
 * 实现回溯法和字典序迭代法两种经典解法
 */
public class LexicographicalPermutation {

    /**
     * 回溯法生成全排列（DFS + 剪枝）
     * @param nums 输入数组（无重复元素）
     * @return 所有排列的列表
     */
    public static List<List<Integer>> permuteBacktrack(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }

        // 先排序，保证字典序
        Arrays.sort(nums);

        boolean[] used = new boolean[nums.length];
        List<Integer> current = new ArrayList<>();

        backtrack(nums, used, current, result);
        return result;
    }

    private static void backtrack(int[] nums, boolean[] used, 
                                   List<Integer> current, List<List<Integer>> result) {
        // 终止条件：已填满所有位置
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 剪枝：跳过已使用的元素
            if (used[i]) {
                continue;
            }

            // 选择元素nums[i]
            used[i] = true;
            current.add(nums[i]);

            // 递归填充下一个位置
            backtrack(nums, used, current, result);

            // 回溯：撤销选择
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }

    /**
     * 字典序迭代法：直接生成下一个排列
     * 原理同C++ STL next_permutation
     */
    public static List<List<Integer>> permuteIterative(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }

        Arrays.sort(nums);

        boolean hasNext = true;
        while (hasNext) {
            // 记录当前排列
            List<Integer> perm = new ArrayList<>();
            for (int num : nums) {
                perm.add(num);
            }
            result.add(perm);

            // 生成下一个字典序排列
            hasNext = nextPermutation(nums);
        }

        return result;
    }

    /**
     * 将当前排列变为下一个字典序排列
     * @return 是否存在下一个排列
     */
    public static boolean nextPermutation(int[] nums) {
        int n = nums.length;

        // 步骤1：从右向左找第一个升序对 nums[i] < nums[i+1]
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // 如果找不到，说明已是最后一个排列
        if (i < 0) {
            // 可选：恢复为第一个排列
            reverse(nums, 0, n - 1);
            return false;
        }

        // 步骤2：从右向左找第一个大于nums[i]的元素
        int j = n - 1;
        while (j > i && nums[j] <= nums[i]) {
            j--;
        }

        // 步骤3：交换
        swap(nums, i, j);

        // 步骤4：反转i之后的部分，使其升序（最小）
        reverse(nums, i + 1, n - 1);

        return true;
    }

    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 left, int right) {
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    /**
     * 获取第k个字典序排列（1-based）
     * 使用康托展开思想，O(n^2)时间
     */
    public static int[] getKthPermutation(int n, int k) {
        // 预计算阶乘
        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        // 可用数字列表
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }

        // k转为0-based索引
        k--;

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            // 确定当前位应该选第几个数字
            int fact = factorial[n - 1 - i];
            int index = k / fact;
            k = k % fact;

            result[i] = numbers.get(index);
            numbers.remove(index);
        }

        return result;
    }

    /**
     * 带重复元素的全排列（需要去重）
     */
    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }

        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        List<Integer> current = new ArrayList<>();

        backtrackUnique(nums, used, current, result);
        return result;
    }

    private static void backtrackUnique(int[] nums, boolean[] used,
                                         List<Integer> current, List<List<Integer>> result) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            // 去重关键：跳过同一层中相同的未使用元素
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }

            used[i] = true;
            current.add(nums[i]);
            backtrackUnique(nums, used, current, result);
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }

    /**
     * 验证结果是否为有效的全排列
     */
    public static boolean validate(List<List<Integer>> permutations, int[] original) {
        int expectedCount = factorial(original.length);
        if (permutations.size() != expectedCount) {
            return false;
        }

        Arrays.sort(original);
        for (List<Integer> perm : permutations) {
            if (perm.size() != original.length) {
                return false;
            }
            int[] arr = perm.stream().mapToInt(Integer::intValue).toArray();
            Arrays.sort(arr);
            if (!Arrays.equals(arr, original)) {
                return false;
            }
        }

        return true;
    }

    private static int factorial(int n) {
        int res = 1;
        for (int i = 2; i <= n; i++) {
            res *= i;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};

        System.out.println("=== 回溯法生成全排列 ===");
        List<List<Integer>> backtrackResult = permuteBacktrack(nums.clone());
        printPermutations(backtrackResult);
        System.out.println("验证: " + (validate(backtrackResult, nums.clone()) ? "通过" : "失败"));

        System.out.println("\n=== 迭代法生成全排列 ===");
        List<List<Integer>> iterativeResult = permuteIterative(nums.clone());
        printPermutations(iterativeResult);
        System.out.println("验证: " + (validate(iterativeResult, nums.clone()) ? "通过" : "失败"));

        System.out.println("\n=== 第4个字典序排列 ===");
        int[] kth = getKthPermutation(3, 4);
        System.out.println("第4个排列: " + Arrays.toString(kth));

        System.out.println("\n=== 含重复元素的全排列 ===");
        int[] dupNums = {1, 1, 2};
        List<List<Integer>> uniqueResult = permuteUnique(dupNums.clone());
        printPermutations(uniqueResult);
        System.out.println("排列数: " + uniqueResult.size() + " (期望: 3)");
    }

    private static void printPermutations(List<List<Integer>> perms) {
        for (int i = 0; i < perms.size(); i++) {
            System.out.printf("  [%d] %s%n", i + 1, perms.get(i));
        }
        System.out.println("总排列数: " + perms.size());
    }
}

时间复杂度分析

两种全排列生成算法的时间复杂度相同，因为都需要输出 $n!$ 个排列，每个排列长度为 $n$。但迭代法的空间效率更优，适合大规模排列生成。

算法应用

字典序全排列在多个领域有重要应用：
– 组合优化：旅行商问题（TSP）的穷举搜索
– 密码学：密钥空间遍历与排列密钥生成
– 生物信息学：DNA序列排列组合分析
– 游戏AI：棋类游戏的走法枚举（如八皇后问题）
– 测试用例生成：软件测试中的参数组合覆盖

拓展思考

对于含重复元素的序列，去重策略是关键。核心思想是：在同一递归层级中，相同的元素只能被选择一次。通过排序后判断 nums[i] == nums[i-1] && !used[i-1] 实现有效去重，确保每个唯一的排列只被生成一次。