C++ std::next_permutation _ 全排列算法函数用法【干货】

时间：2026-07-18

先说几个核心判断。很多人第一次接触 `std::next_permutation` 时，往往会被它看似简单的接口迷惑，以为传入一个容器就能自动生成所有排列。实际上，这恰恰是它最容易被误用的地方——它的行为完全取决于你给它的“初始状态”。

C++ std::next_permutation _ 全排列算法函数用法【干货]

std::next_permutation 必须从升序开始才能枚举全部排列

说句大白话，它不负责帮你找起点，只管从当前状态往下一个字典序排列推。你给它一个 `{2, 1, 3}`，它就从这里开始往后走——生成 `{2, 3, 1}` → `{3, 1, 2}` → `{3, 2, 1}`，然后返回 `false`，并把容器重置为 `{1, 2, 3}`。但问题来了：`{1, 2, 3}`、`{1, 3, 2}` 这些前面的排列已经被漏掉了。

所以正确的做法是：先 `std::sort`，再用 `do-while` 循环把第一次处理也包进去。

std::vector v = {3, 1, 2};
std::sort(v.begin(), v.end()); // 必须有
do {
    // 处理当前排列，比如打印
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
} while (std::next_permutation(v.begin(), v.end()));

这里有几个容易踩的坑：

如果用 `while` 替代 `do-while`，排序后的第一个排列（初始排列）就会被漏掉。
这个函数对 `std::string`、`std::array` 同样适用，但 `std::list` 不行——它需要随机访问迭代器。
如果输入未排序，它仍然会运行，但结果不是全集，而是某个字典序子链，这一点务必要记住。

重复元素时 std::next_permutation 自动去重，但前提是已排序

这个特性其实很实用。它内部按字典序比较并跳过等价排列，不是靠哈希或额外容器去重。举个例子，`{1, 1, 2}` 排序后是 `{1, 1, 2}`，调用 `next_permutation` 全遍历只会输出 3 种排列，而不是 3! = 6 种。这省去了你手动去重的麻烦。

但注意，前提是已经排序。如果初始是 `{1, 2, 1}`（未排序），它仍然会工作，但起点错位，可能导致重复或遗漏。比如先输出 `{2, 1, 1}`，再回到 `{1, 1, 2}`，部分排列被跳过或重复出现。

总结一下要点：

重复元素下，必须先 `std::sort`，否则“自动去重”不成立。
不需要手写 `std::set` 或 `std::unique` 去重，函数内部已经保证结果无重复。
如果用了自定义比较器（比如 `std::greater()`），初始排序方式必须与之一致，否则行为未定义。

std::next_permutation 返回 false 不代表出错，而是“已到底”

这是一个很常见的误解，很多人把 `false` 当成错误码或异常信号。实际上，它只是在告诉你“当前已经是字典序最大排列”，此时函数会将容器重排为最小排列（升序），并返回 `false`。这不是失败，而是设计行为。

看一个典型的错误写法：

if (!std::next_permutation(v.begin(), v.end())) {
    std::cerr << "No more permutations!\n"; // 错！这会误报第一次调用就“没下一个”
    return;
}

记住几个关键点：

`false` 出现在循环末尾是正常终止条件，不是错误分支。
它的时间复杂度是 O(n)，远优于回溯生成全排列的指数开销，适合 n ≤ 10⁴ 的单次推进场景。
如果需要逆序枚举（从大到小），改用 `std::prev_permutation`，但起点必须是降序（`std::sort(v.begin(), v.end(), std::greater())`）。

自定义比较器要小心严格弱序和一致性

当你传入第三个参数 `comp` 时，`std::next_permutation` 会用它判断字典序，但要求这个比较器满足严格弱序，并且必须与你初始化容器时所用的排序方式完全一致。

比如你想按绝对值排列 `{-3, 1, -2}`，不能只写：

auto abs_less = [](int a, int b) { return std::abs(a) < std::abs(b); };
std::sort(v.begin(), v.end(), abs_less);
std::next_permutation(v.begin(), v.end(), abs_less); // 行为未定义！

为什么？因为 `std::next_permutation` 内部实现依赖于“前一个排列能被唯一确定”，而自定义比较器若在相等元素间无法稳定区分（比如 `abs(-2) == abs(2)`），会导致推进逻辑断裂。

安全建议：