每日算法 — 使用java实现下一个排列：字典序生成与线性时间边界扫描

算法背景

下一个排列问题是排列组合中的经典问题：给定一个数字序列，找出这些数字重新排列后的下一个更大的排列。如果不存在更大的排列（即当前已是降序），则返回最小排列（升序）。该问题在LeetCode 31题中非常著名，也是理解字典序排列生成算法的入门题目。

字典序排列在现实中有广泛应用：密码生成、组合测试、遗传算法中的基因编码等场景都需要按字典序遍历所有可能状态。

核心思路

下一个排列的生成遵循以下步骤：

1. 从右向左找第一个升序对：找到最大的索引 i，使得 nums[i] < nums[i+1]。如果找不到，说明数组已是降序，直接反转得到最小排列。
2. 在右侧找最小的大于nums[i]的元素：从右向左找到最大的索引 j，使得 nums[j] > nums[i]。
3. 交换nums[i]和nums[j]：将较大的元素放到前面。
4. 反转i+1到末尾：使后缀变为升序（即最小排列），从而得到下一个字典序排列。

完整Java实现

import java.util.Arrays;

/**
 * 下一个排列算法 - 字典序排列生成
 * 时间复杂度: O(n)  空间复杂度: O(1)
 */
public class NextPermutation {

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int n = nums.length;

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

        // 如果找到了这样的i
        if (i >= 0) {
            // 步骤2: 从右向左找第一个大于nums[i]的元素
            int j = n - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            // 步骤3: 交换
            swap(nums, i, j);
        }

        // 步骤4: 反转i+1到末尾，使其变为升序（最小）
        reverse(nums, i + 1, n - 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    /**
     * 生成从当前排列开始的所有后续排列
     */
    public void printAllPermutations(int[] nums) {
        int[] current = nums.clone();
        int count = 0;
        do {
            System.out.println("排列 " + (++count) + ": " + Arrays.toString(current));
            nextPermutation(current);
        } while (!Arrays.equals(current, nums));
        System.out.println("总排列数: " + count);
    }

    /**
     * 第k个排列 - 结合阶乘分解直接定位
     * 避免生成前面k-1个排列
     */
    public String getPermutation(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索引
        StringBuilder result = new StringBuilder();

        for (int i = n - 1; i >= 0; i--) {
            int index = k / factorial[i];
            k %= factorial[i];
            result.append(numbers.get(index));
            numbers.remove(index);
        }

        return result.toString();
    }

    /**
     * 上一个排列 - 与下一个排列对称
     */
    public void prevPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] <= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = n - 1;
            while (j >= 0 && nums[j] >= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1, n - 1);
    }

    public static void main(String[] args) {
        NextPermutation solution = new NextPermutation();

        // 测试用例1: 基本下一个排列
        int[] nums1 = {1, 2, 3};
        System.out.println("原排列: " + Arrays.toString(nums1));
        solution.nextPermutation(nums1);
        System.out.println("下一个: " + Arrays.toString(nums1));

        // 测试用例2: 需要多处调整
        int[] nums2 = {1, 5, 8, 4, 7, 6, 5, 3, 1};
        System.out.println("\n原排列: " + Arrays.toString(nums2));
        solution.nextPermutation(nums2);
        System.out.println("下一个: " + Arrays.toString(nums2));

        // 测试用例3: 已是最大排列
        int[] nums3 = {3, 2, 1};
        System.out.println("\n原排列: " + Arrays.toString(nums3));
        solution.nextPermutation(nums3);
        System.out.println("下一个(最小): " + Arrays.toString(nums3));

        // 测试用例4: 生成所有排列
        System.out.println("\n生成 [1,2,3] 的所有排列:");
        solution.printAllPermutations(new int[]{1, 2, 3});

        // 测试用例5: 第k个排列
        System.out.println("\n第9个排列(3! = 6个, 取第3个): " + solution.getPermutation(3, 3));
    }
}

复杂度分析

扩展思考

1. 第k个排列优化：使用线段树或树状数组维护可用数字，可以将时间优化到O(n log n)。
2. 有重复元素的下一个排列：上述算法在有重复元素时仍然正确，但全排列数量会变为n!/(k1!×k2!×…)。
3. 循环排列：如果要求首尾相连的最小字典序排列，可以先找到最小元素作为起点，再应用下一个排列。