用 next_permutation 写排列，别再手写递归了

上周帮同事改一段算法题代码，他用了三层嵌套 for 循环硬凑三位数全排列，还加了 set 去重。我顺手替换成两行 sort + next_permutation，运行时间从 87ms 降到 3ms，他盯着屏幕愣了三秒：“这玩意儿……真能直接跳到下一个字典序排列？”

是的，它不仅能，而且不申请额外内存、不递归、不回溯、不判重——只要你的容器支持随机访问（比如 vector、array、string），它就直接在原地“拧”出下一个排列。

但很多人第一次用，会卡在几个真实痛点上：

• 调用前忘了 sort，结果只输出一两个排列就停了；
• 把 next_permutation 当成“生成所有排列”的黑盒，却没意识到它依赖初始状态；
• 遇到重复元素时，发现输出里有重复排列，误以为函数有 bug。

我们来把这事说透。

next_permutation 的核心逻辑其实很“人话”：
找最后一个“能变大的位置”，把它换成后面比它大、但尽可能小的数，再把后面的数翻转成升序。
比如 [1,3,2]：

• 从右往左找第一个下降点 → 1（因为 3>2，但 1<3）；
• 在 3,2 中找比 1 大的最小值 → 2；
• 交换得 [2,3,1]；
• 把 3,1 翻转 → [2,1,3]。

这个过程天然保证了字典序严格递增，也天然跳过了重复排列——前提是输入序列本身已排序，且你按顺序调用。

所以第一铁律：必须先 sort(begin, end)，再进循环。
不是“建议”，是“必要”。否则它从任意起点开始，大概率在几轮后返回 false，你以为跑完了，其实只扫了冰山一角。

vector<int> a = {3, 1, 2};
sort(a.begin(), a.end()); // 关键！
do {
    // 处理当前排列 a
} while (next_permutation(a.begin(), a.end()));

注意：do-while 是安全选择，因为 next_permutation 对已排序数组调用一次，会生成第二个排列，并返回 true；而 while 写法需要先手动输出初始态，稍不注意就漏掉第一个。

重复元素怎么办？比如 {1,1,2}。
答案是：它本来就能正确去重，只要你给的是排好序的输入。
next_permutation 的实现里，找“下一个更大值”时，会跳过相等元素；翻转时也只操作后缀。所以 {1,1,2} 经 sort 后是 [1,1,2]，调用流程是：
[1,1,2] → [1,2,1] → [2,1,1] → false。
刚好 3 种，不是 6 种。
它不是靠哈希或 set 去重，而是靠字典序跳跃逻辑天然规避重复——这点常被忽略，却恰恰是它比手写 DFS 更优雅的地方。

实战中容易踩的坑：

• 传 vector<int> 时，别传 vector<int>&& 或临时对象，next_permutation 要修改原容器；
• 处理字符串时，string s = "bac"，记得先 sort(s.begin(), s.end())，否则 "bac" 排列只输出 "bca" 就停了；
• 如果你需要第 k 个排列（比如面试题“求字典序第 k 小排列”），别用 next_permutation 循环 k 次——k 可能是 1e9，超时。那是数学题，该用阶乘数系统解。

另外，next_permutation 返回 bool，不是 void。务必检查返回值。有人写成：

while (next_permutation(a.begin(), a.end())) {
    // ...
}

如果初始数组就是最大排列（如 [3,2,1]），循环一次都不进，直接跳过——连 [3,2,1] 本尊都丢了。

最后说个少有人提的细节：
next_permutation 对自定义类型也有效，只要你的 < 运算符定义合理。比如你有个 struct Point {int x,y;}，想按 x+y 排序生成排列，只需重载 operator< 比较 x+y，然后 sort + next_permutation 照常工作。它不关心你是 int 还是结构体，只认大小关系。

这说明什么？它本质是个基于比较的、泛型的字典序游标，不是专为数字设计的玩具函数。

下次遇到排列需求，别急着翻出那套“选一个、标记、递归、回溯、清标记”的模板。
先花 10 秒 sort，再用 do-while 包住 next_permutation。
省下的不仅是代码行数，更是调试时对着重复输出抓耳挠腮的时间。

它不炫技，不抽象，就老老实实按字典序一步步走——而多数时候，最朴素的路径，恰恰最可靠。