全排列与字典序：Next Permutation、Permutation Sequence、Gray Code

摘要

本篇覆盖三道以”序列与数学规律”为核心的数组题：Next Permutation（LeetCode 31）、Permutation Sequence（LeetCode 60）和 Gray Code（LeetCode 89）。这三道题的共同点是：不能靠暴力枚举，必须理解排列的数学结构。Next Permutation 考察字典序的递增规律；Permutation Sequence 引入阶乘数系，能直接跳转到第 k 个排列而无需生成所有排列；Gray Code 则利用二进制格雷码的对称递推性质。这些题目在面试中属于”能做出来就是加分项，做不出来也不丢人”的范畴，但理解它们能显著拓宽你的算法视野。

第 1 章字典序：排列的全序关系

1.1 什么是字典序

字典序（Lexicographic Order）是一种排列的比较方式，类比字典中单词的排列顺序：先比较第一个字符，相同则比第二个，以此类推。

对于排列 $[1, 2, 3]$ 的所有全排列，按字典序排列如下：

1. [1, 2, 3]
2. [1, 3, 2]
3. [2, 1, 3]
4. [2, 3, 1]
5. [3, 1, 2]
6. [3, 2, 1]

可以发现：

最小排列：升序 [1,2,3]
最大排列：降序 [3,2,1]
给定任意一个排列，其”下一个”排列是字典序紧接着它的那一个

1.2 排列的数量

对 $n$ 个不同元素，全排列共有 $n!$ 种。常见的 $n!$ ：

$3! = 6$
$4! = 24$
$5! = 120$
$10! = 3, 628, 800$

$n = 13$ 时 $13! \approx 6 \times 1 0^{9}$ ，超过 int 范围； $n = 20$ 时 $20! \approx 2.4 \times 1 0^{18}$ ，超过 long 范围。这在题目中有实际意义：不能用整数直接表示排列的编号。

第 2 章 LeetCode 31：下一个排列

2.1 题目

LeetCode 31 - Next Permutation（中等）

整数数组的一个排列是其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。

整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即升序排列）。

原地修改，使用常数额外空间。

输入: nums = [1,2,3]  →  输出: [1,3,2]
输入: nums = [3,2,1]  →  输出: [1,2,3]（已是最大，回到最小）
输入: nums = [1,1,5]  →  输出: [1,5,1]

2.2 推导算法：观察字典序递增的规律

关键问题：给定排列 [1,2,3]，下一个是 [1,3,2]，为什么？

观察这两个排列的差异：只有后两位发生了变化（2,3 → 3,2），前缀 1 保持不变。这意味着：下一个排列应该尽量保留长的公共前缀，只在尽量靠后的位置做最小的改动。

更一般地，找下一个排列的三步法：

第一步：从右向左找第一个”下降位”（即满足 nums[i] < nums[i+1] 的最大 i）

为什么从右向左？因为我们想尽量保留前缀。从右向左找第一个不满足”非严格降序”的位置 i，即 nums[i] < nums[i+1]。

[1, 2, 3] → 从右找：nums[1]=2 < nums[2]=3，找到 i=1

如果整个数组都是严格降序（如 [3,2,1]），找不到这样的 i，说明已经是最大排列，直接翻转整个数组（变为最小排列）。

第二步：在 nums[i] 右侧（i+1 到末尾），找比 nums[i] 大的最小元素，记为 nums[j]

右侧区间 [i+1, n-1] 是严格降序的（因为 i 是最右的下降位）。在降序序列里找”比 nums[i] 大的最小元素”，从右向左扫找到第一个大于 nums[i] 的 nums[j]。

nums[i=1]=2，右侧是 [3]，找比 2 大的最小值：j=2（nums[2]=3）

第三步：交换 nums[i] 和 nums[j]，然后翻转 i+1 到末尾的区间

交换后，nums[i] 变成了”比原来大一点点”的值，实现了”最小增大”。翻转 i+1 到末尾的区间（原来是降序，翻转后变升序），确保这部分是最小排列，整体构成”下一个最小的排列”。

[1,2,3] → 交换 i=1,j=2：[1,3,2] → 翻转 [2:]：只有一个元素 [2]，不变 → [1,3,2] ✓

更复杂的例子：[1,3,5,4,2]

从右找下降位: nums[1]=3 < nums[2]=5 → i=1 (但 nums[2]=5 > nums[3]=4, 继续找)
             等等，应该找 "最右" 的下降位:
             
从右向左: nums[4]=2, nums[3]=4 (4>2，不是下降), nums[2]=5 (5>4，不是下降), 
         nums[1]=3 (3<5，是下降！) → i=1

右侧 [5,4,2] 是降序，找比 nums[i=1]=3 大的最小值：
  从右向左：nums[4]=2 (不大于3), nums[3]=4 (大于3！) → j=3

交换 i=1, j=3: [1,4,5,3,2]

翻转 [i+1, end] = [5,3,2] → [2,3,5]

结果: [1,4,2,3,5] ✓

验证：[1,3,5,4,2] 的下一个排列应该是 [1,4,2,3,5]（比 13542 大且最接近的序列），正确。

2.3 代码实现

public void nextPermutation(int[] nums) {
    int n = nums.length;
    
    // 第一步：从右向左找第一个下降位 i（nums[i] < nums[i+1]）
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    
    if (i >= 0) {
        // 第二步：在右侧找比 nums[i] 大的最小元素 j
        int j = n - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        // 交换 i 和 j
        swap(nums, i, j);
    }
    
    // 第三步：翻转 i+1 到末尾（如果 i<0，翻转整个数组，因为是最大排列→最小排列）
    reverse(nums, i + 1, n - 1);
}
 
private void swap(int[] nums, int i, int j) {
    int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
}
 
private void reverse(int[] nums, int left, int right) {
    while (left < right) {
        swap(nums, left++, right--);
    }
}

复杂度：时间 $O (n)$ ，空间 $O (1)$ 。

第 3 章 LeetCode 60：第 k 个排列

3.1 题目

LeetCode 60 - Permutation Sequence（困难）

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列，按大小顺序列出所有排列情况，并一一标记，返回第 k 个排列。

输入: n=3, k=3
输出: "213"（[1,2,3]全排列的字典序是 123,132,213,231,312,321，第3个是213）

输入: n=4, k=9
输出: "2314"

3.2 为什么不能反复调用 Next Permutation

最直接的思路：从第一个排列 [1,2,...,n] 开始，反复调用 Next Permutation，调用 k-1 次后得到第 k 个排列。

但 k 最大是 $n! = 362880$ （ $n = 9$ ），每次 Next Permutation 是 $O (n)$ ，总时间 $O (n \cdot n!)$ ，对于 $n = 9$ 是约 $3 \times 1 0^{6}$ ，可以接受，但不够优雅。而且题目 n 可以到 9， $9! = 362880$ ，暴力方法边界还行；但如果 $n = 13$ ， $13! \approx 6 \times 1 0^{9}$ ，肯定超时。

3.3 阶乘数系（Factoradic Number System）

核心思路：不用生成 k-1 个排列，而是直接算出第 k 个排列的每一位。

对 n 个数字的全排列，按字典序排列后，它们可以分成 $n$ 组，每组有 $(n - 1)!$ 个排列（第一位分别是 1、2、3…n）。

第 1 到 $(n - 1)!$ 个排列的第一位是最小的数字
第 $(n - 1)! + 1$ 到 $2 \cdot (n - 1)!$ 个排列的第一位是第二小的数字
…

因此，第一位的索引（在剩余数字列表中）是 (k-1) / (n-1)!，取整。

确定第一位后，k 更新为 (k-1) % (n-1)!，然后在剩余 $n - 1$ 个数字中，用同样的方式确定第二位，以此类推。

这就是阶乘数系的本质：用 $(n - 1)!, (n - 2)!, ..., 1!, 0!$ 作为进位单位，对 $k - 1$ 进行分解。

3.4 手动演算

n=4, k=9，数字列表 [1,2,3,4]：

阶乘： $3! = 6, 2! = 2, 1! = 1, 0! = 1$

第一位：(k-1) / (n-1)! = (9-1)/6 = 8/6 = 1（整除取商），选第 1 个数字（0-indexed）→ 数字 2 更新 k = 8 % 6 = 2，剩余数字 [1,3,4]

第二位：(k-1) / (n-2)! = (2-1)/2 = 1/2 = 0，选第 0 个数字 → 数字 1 更新 k = 1 % 2 = 1，剩余数字 [3,4]

第三位：(k-1) / (n-3)! = (1-1)/1 = 0/1 = 0，选第 0 个数字 → 数字 3 更新 k = 0 % 1 = 0，剩余数字 [4]

第四位：只剩 [4]，选 4

结果：2314 ✓

3.5 代码实现

public String getPermutation(int n, int k) {
    // 预计算阶乘
    int[] factorial = new int[n];
    factorial[0] = 1;
    for (int i = 1; i < n; i++) {
        factorial[i] = factorial[i - 1] * i;
    }
    
    // 数字列表（可用 ArrayList 方便删除）
    List<Integer> digits = new ArrayList<>();
    for (int i = 1; i <= n; i++) digits.add(i);
    
    k--; // 转为 0-indexed
    StringBuilder sb = new StringBuilder();
    
    for (int i = n; i >= 1; i--) {
        int idx = k / factorial[i - 1]; // 当前位选第几个数字
        sb.append(digits.get(idx));
        digits.remove(idx);            // 移除已选的数字
        k %= factorial[i - 1];         // 更新 k
    }
    
    return sb.toString();
}

复杂度：时间 $O (n^{2})$ （每次 digits.remove 是 $O (n)$ ，共 $n$ 次），空间 $O (n)$ 。这远比反复调用 Next Permutation 高效（ $O (n^{2})$ vs $O (n \cdot n!)$ ）。

第 4 章 LeetCode 89：格雷编码

4.1 题目

LeetCode 89 - Gray Code（中等）

n 位格雷码序列 是一个由 $2^{n}$ 个整数组成的序列，其中：

每个整数都在范围 [0, 2^n - 1] 内（含 0 和 $2^{n} - 1$ ）
第一个整数是 0
一个整数在序列中出现不超过一次
每对相邻整数的二进制表示恰好一位不同（第一个和最后一个整数也视为相邻）

返回任意一个有效的 n 位格雷码序列。

输入: n = 2
输出: [0,1,3,2]（二进制: 00→01→11→10，相邻只差一位）

输入: n = 1
输出: [0,1]

4.2 格雷码的数学性质

格雷码（Gray Code）最初由贝尔实验室工程师 Frank Gray 在 1953 年发明，原始用途是减少机械式编码器中由于多位同时翻转导致的短暂错误状态。

核心性质：第 $i$ 个格雷码 = $i \oplus (i >> 1)$

其中 $\oplus$ 是异或运算， $>>$ 是右移。这个公式可以直接生成 n 位格雷码序列：

i=0: 0 XOR 0 = 0  (00)
i=1: 1 XOR 0 = 1  (01)
i=2: 2 XOR 1 = 3  (11)
i=3: 3 XOR 1 = 2  (10)

即 [0, 1, 3, 2]，这就是 n=2 的格雷码序列。

4.3 公式的推导：镜像反射递推

为什么 $G (i) = i \oplus (i >> 1)$ ？理解这个公式，需要看格雷码的递推结构：

$n = 1$ ：[0, 1]（1 位）
$n = 2$ ：在 $n = 1$ 的基础上：先复制一遍（前面加 0），再倒序复制一遍（前面加 1）
- 原序列 [0, 1] 前加 0 → [00, 01]
- 倒序后前加 1 → [11, 10]
- 合并：[00, 01, 11, 10] = [0, 1, 3, 2]

这种”镜像折叠”的构造方式确保：

两段接合处（01 和 11）只差一位（最高位从 0 变 1）✓
每段内部相邻元素也只差一位（继承自上一级的性质）✓
首尾（00 和 10）也只差一位（最高位）✓

归纳可证： $G (i) = i \oplus (i >> 1)$ 生成的序列等价于这个镜像递推。

4.4 代码实现

public List<Integer> grayCode(int n) {
    List<Integer> result = new ArrayList<>();
    // 2^n 个格雷码，直接用公式生成
    for (int i = 0; i < (1 << n); i++) {
        result.add(i ^ (i >> 1));
    }
    return result;
}

简洁到令人惊叹的三行代码（for + add），时间 $O (2^{n})$ ，空间 $O (2^{n})$ （存储结果）。

4.5 镜像递推的代码实现（另一种思路）

如果你在面试中忘了 i ^ (i >> 1) 这个公式，可以用镜像递推从小到大构建：

public List<Integer> grayCode(int n) {
    List<Integer> result = new ArrayList<>();
    result.add(0); // 0 位时：[0]
    
    for (int i = 0; i < n; i++) {
        int size = result.size();
        // 把当前序列倒序复制，每个元素最高位加 1（即加 2^i）
        for (int j = size - 1; j >= 0; j--) {
            result.add(result.get(j) + (1 << i));
        }
    }
    
    return result;
}

这个实现更直观地展示了镜像递推的过程，复杂度相同但每步结果更容易跟踪。

第 5 章三道题的关联与面试策略

5.1 共同的底层思想

题目	核心数学思想	关键操作
Next Permutation	字典序递增的最小改动原则	找下降位、找替换位、翻转后缀
Permutation Sequence	阶乘数系（位置 = 编号的阶乘分解）	`(k-1) / (n-1)!` 确定每位
Gray Code	镜像递推 / `i ^ (i>>1)` 公式	递推或直接公式

三道题都不需要回溯，也不需要 DFS，而是利用数学结构直接构造答案，这是它们的共同特点。

5.2 面试应对

Next Permutation：背下三步法（找下降位、找替换位、翻转后缀），这是面试中最可能被考到的。
Permutation Sequence：理解阶乘数系的”进位”类比（类似十进制的位权），推导过程比记忆公式更可靠。
Gray Code：能背下 i ^ (i >> 1) 公式最好，否则用镜像递推也能得分。

设计哲学：数学洞察 vs 工程暴力

这三道题有一个共同特点：暴力解法（反复调用 next、生成所有排列再取第 k 个、BFS/DFS 构造格雷码）都能做出来，但有更优雅的数学解法。面试中展示数学洞察力，往往比写出能跑的暴力代码更能打动面试官。

下一篇预告

07 矩阵数组专题：Rotate Image、Set Matrix Zeroes、Valid Sudoku 将进入二维数组的世界。旋转矩阵、置零矩阵和数独校验看起来是三道不相关的题，但它们都围绕一个核心：如何在不使用额外空间（或极小额外空间）的前提下，对二维数组进行原地修改。

汀的知识碎片

文章导航

06 全排列与字典序：Next Permutation、Permutation Sequence、Gray Code

全排列与字典序：Next Permutation、Permutation Sequence、Gray Code

摘要

第 1 章字典序：排列的全序关系

1.1 什么是字典序

1.2 排列的数量

第 2 章 LeetCode 31：下一个排列

2.1 题目

2.2 推导算法：观察字典序递增的规律

2.3 代码实现

第 3 章 LeetCode 60：第 k 个排列

3.1 题目

3.2 为什么不能反复调用 Next Permutation

3.3 阶乘数系（Factoradic Number System）

3.4 手动演算

3.5 代码实现

第 4 章 LeetCode 89：格雷编码

4.1 题目

4.2 格雷码的数学性质

4.3 公式的推导：镜像反射递推

4.4 代码实现

4.5 镜像递推的代码实现（另一种思路）

第 5 章三道题的关联与面试策略

5.1 共同的底层思想

5.2 面试应对

下一篇预告

On this page

Backlinks

汀的知识碎片

文章导航

06 全排列与字典序：Next Permutation、Permutation Sequence、Gray Code

全排列与字典序：Next Permutation、Permutation Sequence、Gray Code

摘要

第 1 章 字典序：排列的全序关系

1.1 什么是字典序

1.2 排列的数量

第 2 章 LeetCode 31：下一个排列

2.1 题目

2.2 推导算法：观察字典序递增的规律

2.3 代码实现

第 3 章 LeetCode 60：第 k 个排列

3.1 题目

3.2 为什么不能反复调用 Next Permutation

3.3 阶乘数系（Factoradic Number System）

3.4 手动演算

3.5 代码实现

第 4 章 LeetCode 89：格雷编码

4.1 题目

4.2 格雷码的数学性质

4.3 公式的推导：镜像反射递推

4.4 代码实现

4.5 镜像递推的代码实现（另一种思路）

第 5 章 三道题的关联与面试策略

5.1 共同的底层思想

5.2 面试应对

下一篇预告

On this page

Backlinks

第 1 章字典序：排列的全序关系

第 5 章三道题的关联与面试策略