我的算法书 - 非递归生成排列

一句话算法

next_permutation 就是把当前排列变成“刚好比它大一点”的下一个排列。

问题模型

给定一个排列，按字典序生成它的下一个排列。

例如排列按字典序从小到大为：

如果当前排列是 2 1 3，下一个排列就是 2 3 1。

这个方法可以从最小排列开始，不使用递归，依次生成所有排列。

核心直觉

从右往左看，一个后缀如果是降序的，例如：

5 4 3

它已经是这些元素能组成的最大顺序，单独调整这个后缀不可能让整个排列变大一点。

所以我们要找最靠右的一个位置 i，满足：

a[i] < a[i + 1]

这个位置就是“还能变大”的交换点。

为了让新排列只变大一点：

在右侧后缀里找最靠右的、比 a[i] 大的数。
交换它们。
把后缀反转成升序，让后缀尽量小。

算法步骤

对数组 a[0..n-1]：

从右向左找到第一个 i，满足 a[i] < a[i + 1]。
如果找不到，说明整个排列已经降序，它是最后一个排列。
从右向左找到第一个 j，满足 a[j] > a[i]。
交换 a[i] 和 a[j]。
反转区间 a[i+1..n-1]。

“为什么找最右边”

越靠右的位置权重越小。先尽量改变靠右的位置，才能保证得到的是“刚好大一点”的排列。

算法证明

关键不变量： 找到交换点 i 后，后缀 a[i+1..n-1] 一定是非递增的。

i 是从右往左第一个满足 a[i] < a[i+1] 的位置。
因此在 i 右边，不存在更靠右的上升位置。
所以后缀 a[i+1..n-1] 是非递增的，也就是该后缀当前能组成的最大字典序。

接下来说明操作得到的就是下一个排列：

要让排列变大，必须把某个位置换成更大的数。
为了增量最小，应该选择最靠右还能变大的位置，也就是 i。
后缀是非递增的，从右往左找到的第一个 > a[i] 的数，就是后缀中大于 a[i] 的最小值。
交换后，前缀只在位置 i 变大了最小可能值。
此时后缀仍然是非递增的，反转后变成非递减，也就是后缀的最小字典序。

所以整个排列变大了，并且没有任何排列能夹在旧排列和新排列之间。

复杂度分析

时间复杂度： $O(n)$ ，最多扫描两次数组并反转一次后缀。
空间复杂度： $O(1)$ ，只使用常数个额外变量。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

        #include <bits/stdc++.h>
using namespace std;

// Manual implementation of lexicographic next_permutation.
// It returns false when the current sequence is already the last permutation.
bool next_permutation_manual(vector<int> &a) {
    int n = (int)a.size();

    // 1. Find the rightmost position i with a[i] < a[i + 1].
    // The suffix a[i + 1..n - 1] is non-increasing.
    int i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) --i;
    if (i < 0) return false;

    // 2. Find the rightmost element larger than a[i].
    int j = n - 1;
    while (a[j] <= a[i]) --j;

    // 3. Make the permutation slightly larger, then minimize the suffix.
    swap(a[i], a[j]);
    reverse(a.begin() + i + 1, a.end());
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) a[i] = i + 1;

    do {
        for (int i = 0; i < n; ++i) {
            if (i) cout << ' ';
            cout << a[i];
        }
        cout << '\n';
    } while (next_permutation_manual(a));

    return 0;
}

测试用例

输入：

输出：

应用分类详解

非递归排列生成的本质是：在字典序中不断找下一个状态。

一、按字典序输出所有排列

典型模式： 要求排列从小到大输出，或者要求与 C++ next_permutation 一致。

识别信号： 题面出现“字典序”“下一个排列”“非递归生成排列”。

核心建模： 当前数组就是状态，每次把状态推进到字典序的下一个。

应用场景	经典题目	核心思路
输出全排列	luogu-P1706	从 `1..n` 开始不断求下一个排列
下一个排列	leetcodecn-31	原地修改为下一个字典序排列

二、状态空间按顺序遍历

典型模式： 每个排列代表一个状态，要按确定顺序枚举并计算。

识别信号： n 较小，顺序敏感，不需要递归剪枝。

核心建模： 用排列表示访问顺序、任务顺序或映射关系，每次推进一个排列。

应用场景	经典题目	核心思路
小规模暴力最优顺序	TSP 入门模型	枚举城市访问顺序并取最小代价
排列状态模拟	竞赛模拟题	每个排列作为一个完整方案检查

经典例题

leetcodecn-31 下一个排列：直接考察本算法的原地版本。
luogu-P1706 全排列问题：既可以 DFS，也可以用本页方法非递归输出。
leetcodecn-46 全排列：对比递归回溯和字典序迭代两种写法。

参考

本书相关章节：全排列