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

先说几个核心判断。很多人第一次接触 `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)`），会导致推进逻辑断裂。

安全建议：

• 仅当所有元素在 `comp` 下两两可比、且无等价类干扰字典序推进时，才安全使用。
• 多数情况下，用默认 `operator<` 最稳妥。如果确实需要定制，优先考虑预处理映射，比如转为索引+权重数组。
• 结构体排序更危险：若 `comp` 只比较字段 A，但字段 B 不同，`next_permutation` 可能生成语义重复却内存不同的排列。

实际用起来，最容易被忽略的点是：它不关心你的业务含义，只机械地执行字典序推进。哪怕你传的是带 ID 的对象，只要比较器没覆盖全部判据，它就可能把两个逻辑不同但比较结果相同的对象当作同一个排列跳过——这种 bug 往往只在数据含边界值时才会暴露。