刷算法题也好写实际业务代码也好只要碰到“把一堆元素的所有排列都列出来”这种需求C 选手脑子里第一时间蹦出来的基本就是next_permutation和prev_permutation这两个函数。它们藏在algorithm头文件里用起来一行就能推进一步看起来简单到没什么可讲的。但我带过的新人里十个有八个第一次用都会踩坑要么少输出一个排列要么结果里莫名其妙缺了几种情况要么在自定义比较器上栽跟头。这篇就把这两个函数从接口约定、内部机制、实操写法到排查经验一次讲透适合刚接触 STL 的同学也适合用了很久但没细究过原理的老手对照着看一遍。我尽量不写教科书式的定义而是按照“当时为什么这么写、踩过什么坑、后来怎么改”的顺序来讲。1. 需求拆解与方案选型为什么最后选了标准库1.1 手写全排列最常翻车的三个地方在真正理解next_permutation的价值之前得先知道手写一个全排列生成器有多容易出错。我见过最常见的手写方案是递归回溯思路本身没问题但落地的时候问题一堆。第一个坑是状态恢复不干净。递归回溯的核心是“选一个、往下走、撤销选择”撤销这一步只要写漏一行pop_back()或者忘记把used[i]置回false结果就会莫名其妙地少一大堆。更麻烦的是这种 bug 往往不会崩溃只是静默地少输出你不逐条比对根本发现不了。第二个坑是去重逻辑写复杂。序列里带重复元素的时候回溯法必须先排序然后在每一层判断if (i 0 a[i] a[i-1] !used[i-1]) continue;这种剪枝。这个条件我见过太多人写反写成used[i-1]就会漏解写成!used[i-1]又可能重复。而且这个剪枝只对“排序后 相邻相同”的输入成立换个场景就失效。第三个坑是顺序不可控。手写回溯生成的顺序取决于你的循环怎么写可能是字典序也可能不是。如果题目要求按字典序输出你还得额外排一次序或者在递归里保证从小到大枚举。这些加起来代码量轻松三四十行而标准库只给你两行。1.2 三种方案的正面对比我把常见的三种做法拉出来对比一下这样选型的理由会更清楚。方案代码量去重能力输出顺序适配自定义类型典型风险递归回溯30 行以上需要手写剪枝取决于实现需要自己处理状态恢复漏写、剪枝写反手写字典序推进20 行左右天然去重严格字典序需要重载比较边界条件写错next_permutation3 行天然去重严格字典序传比较器即可初始序列未排序表格里最后一列的“典型风险”其实就是我后面要重点讲的排查方向。可以看到标准库方案把“去重”和“顺序”这两个最容易出问题的点直接吃掉了剩下的风险只剩一个你得记得先排序。这里解释一下为什么标准库天然去重。next_permutation判断两个元素是否“相等”用的是!(a b) !(b a)也就是说它只认严格弱序。当两个元素在比较器眼里完全等价时算法不会去交换它们的位置因此同一个多重集合只会被生成一次。这个性质非常关键后面第 3 章讲重复元素时还会展开。1.3 两个函数的接口约定与边界先把签名摆清楚这是后面所有讨论的基础。template class BidirIt bool next_permutation(BidirIt first, BidirIt last); template class BidirIt, class Compare bool next_permutation(BidirIt first, BidirIt last, Compare comp); template class BidirIt bool prev_permutation(BidirIt first, BidirIt last);几个必须记住的约定迭代器要求是双向迭代器BidirectionalIteratorstd::list、std::vector、原生数组、std::string都满足std::forward_list不满足因为算法末尾需要反向遍历。返回值是bool表示“是否存在下一个排列”。返回false的时候区间已经被重排成该序列的最小对next_permutation或最大对prev_permutation排列这一点极其重要很多循环写法就靠它。空区间和单元素区间返回false但不会做任何修改。时间复杂度最坏 O(n)均摊 O(1)——均摊这个说法很多人不理解意思是枚举完所有排列的总代价是 O(n!·n)平摊到每一步大约是常数倍的交换加一次局部反转。注意next_permutation返回false时序列会被“绕回”到最小排列这是标准行为不是未定义。如果你把返回值当作“是否还有下一轮”来控制循环这个绕回动作正好被do-while的结构吃掉但如果你手动判断返回值再决定要不要继续用这个序列就要小心它已经被改写了。2. 内部机制字典序到底是怎么一步步往前挪的2.1 “下一个排列”的严格定义想搞懂这个函数得先把“下一个”这三个字定义清楚。给定一个序列把它所有不同的排列按字典序从小到大排成一列当前序列后面的那一个就是“下一个排列”。如果当前已经是最大的那个就没有下一个。举个两元素的例子[1, 2]的下一个是[2, 1][2, 1]没有下一个。三元素[1, 2, 3]的完整序列是1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1一共 6 个正好是 3!。这个数量和元素是否重复无关——如果输入是[1, 1, 2]只有 3 个不同排列1 1 2、1 2 1、2 1 1。next_permutation会自动帮你跳过那些因为交换相等元素而产生的重复项。从“字典序”这个词本身就能推出一条重要性质任意序列的下一个排列是在保持前缀尽可能长的前提下把后缀调整成最小的那个更大排列。这个直觉直接对应了后面的四步算法。2.2 四步走算法的拆解标准库的实现libstdc 和 libc 思路一致可以拆成四步我按执行顺序写第一步从右往左找第一对“升序邻居”。也就是找最大的下标i满足a[i] a[i1]。如果找不到说明整个序列是单调不增的它已经是字典序最大的排列函数返回false。为什么这么找因为从右往左第一个a[i] a[i1]的位置意味着a[i]右边那一段是完全非递增的也就是右边那段已经是它自己能达到的最大排列了。想让整体变大唯一的办法就是动a[i]这一位。第二步从右往左找第一个比a[i]大的元素。也就是找最大的下标j满足a[j] a[i]。由于第一步已经确认a[i1..end]是单调不增的从右往左扫遇到的第一个大于a[i]的元素就是最小的那个大于a[i]的元素。这一步选中的就是“刚好大一点点”的替换值。第三步交换a[i]和a[j]。交换之后a[i]这一位变成了后缀里能选的最小可行值前缀部分保持不变。第四步把i1到末尾这一段反转。因为交换之后a[i1..end]仍然是单调不增的这一点需要一点推理但结论成立而我们要的是“下一个”排列也就是后缀要尽可能小所以直接反转成单调不减即可。这四步合起来逻辑非常紧凑而且每一步都有明确的必要性。我特别喜欢拿它给新人讲“算法设计”这个概念因为它没有一个多余的动作每一步都在解决一个具体约束。2.3 拿一个具体序列手推一遍纸上推一遍比看十遍代码管用。拿[1, 3, 5, 4, 2]走一遍。第一步从右往左找升序邻居4 2不成立。5 4不成立。3 5成立i 1值 3。此时后缀[5, 4, 2]确实是单调不增的符合预期。第二步从右往左找第一个大于 3 的元素2 3不成立。4 3成立j 3值 4。注意4 是后缀里比 3 大的元素中最小的那个。第三步交换a[1]和a[3]序列变成[1, 4, 5, 3, 2]。第四步反转i1到末尾也就是反转[5, 3, 2]得到[1, 4, 2, 3, 5]。验证一下[1, 3, 5, 4, 2]的下一个字典序排列确实是[1, 4, 2, 3, 5]。前缀1不变第二位从 3 变成 4最小可行增量后缀被压到最小。再推一个边界情况[3, 2, 1]。第一步扫完找不到升序邻居直接返回false同时把序列反转成[1, 2, 3]。这就是标准里说的“绕回最小排列”。这个行为是next_permutation能配合do-while使用的根本原因。2.4 复杂度与常数开销时间上第一步和第二步各扫一遍后缀最坏 O(n)第四步反转也是 O(n)。但由于反转只在真正发生替换时执行且后缀长度在大量枚举中平均很短所以标准把它的均摊复杂度标为 O(1)。整体枚举n!个排列的总时间是 O(n!·n)。空间上是 O(1)不需要额外容器。这一点在手写回溯时是做不到的——回溯至少要维护一个used数组和一个路径栈空间 O(n)。有个实际影响值得说因为每次推进都要从右往左扫描序列越长、越接近有序单次推进的平均代价就越低。如果你枚举一个 10 元素的序列总共有 360 万多个排列全部跑一遍大概在几百毫秒级别这个量级在竞赛和脚本工具里完全够用。但如果是 13 元素62 亿个排列那就不是算法问题而是你根本不该枚举。注意prev_permutation的四步是next_permutation的严格镜像——找第一个a[i] a[i1]找第一个a[j] a[i]交换反转。所有关于“下一个”的推理换成“上一个”都成立我不再重复推演但请务必自己动手推一遍很多人对prev的理解停留在“反过来”真上手就写错初始化。3. 上手实操从最小例子到工程封装3.1 最小可用样例与循环骨架先给一个能直接跑的最小例子。#include algorithm #include iostream #include vector int main() { std::vectorint a{1, 2, 3}; std::sort(a.begin(), a.end()); // 关键必须先排成升序 do { for (int x : a) std::cout x ; std::cout \n; } while (std::next_permutation(a.begin(), a.end())); return 0; }这段代码有几个细节值得逐条说。第一为什么用do-while而不是while。next_permutation的作用是“把当前序列推进到下一个”它不会生成当前这个序列。而你要枚举的恰恰包括初始序列本身。所以第一次循环体必须先执行一遍输出初始序列然后再推进。用while写就是while (next_permutation(...))这会把第一个排列漏掉导致少输出一个。这是新人最高频的错误没有之一。第二sort不能省。next_permutation假设你从最小排列开始它只会往“更大”的方向走。如果你的初始序列是[3, 1, 2]那它只会生成[3, 2, 1]然后就结束了前面那一堆[1, 2, 3]、[1, 3, 2]、[2, 1, 3]全部丢掉。这个问题下面第 4 章会专门讲。第三如果想从最大排列开始倒着枚举就把sort换成sort(a.begin(), a.end(), std::greaterint())然后把next_permutation换成prev_permutation循环结构不变。3.2 重复元素与去重带重复元素的场景比想象中常见比如给你一个字符串aab要求输出所有不同的排列或者给你一堆货物的重量可能有相同的。这时候直接用next_permutation就是正确结果不需要任何额外处理。#include algorithm #include iostream #include string int main() { std::string s aabb; std::sort(s.begin(), s.end()); int count 0; do { std::cout s \n; count; } while (std::next_permutation(s.begin(), s.end())); std::cout total: count \n; // 输出 6 }aabb的不同排列数是 4!/(2!·2!) 6结果正好是 6 个。如果你换成手写回溯而没有正确剪枝很可能会输出 24 个把两个 a 和两个 b 当成不同的。原理在第 1.2 节提过算法在找a[j] a[i]用的是严格大于在找升序邻居用的是严格小于等于的情况一律跳过。这意味着两个等价元素永远不会被互相交换因此同一排列只会出现一次。提示如果你希望把重复元素当成不同元素来枚举比如元素是带 id 的结构体虽然值相同但代表不同对象那就需要把 id 也纳入比较否则会被判为等价而合并。这是个容易被忽略的语义差异。3.3 自定义比较器与结构体next_permutation支持传入比较器但用法比sort更容易错。先看一个正确的例子。#include algorithm #include iostream #include vector struct Item { int weight; char label; }; int main() { std::vectorItem items{{2, b}, {1, a}, {3, c}}; auto cmp [](const Item x, const Item y) { return x.weight y.weight; // 严格弱序 }; std::sort(items.begin(), items.end(), cmp); do { for (const auto it : items) std::cout it.label; std::cout \n; } while (std::next_permutation(items.begin(), items.end(), cmp)); }关键点比较器必须是严格弱序并且要和排序时用的是同一个。这两条只要有一条不满足结果就会出问题。严格弱序的意思是对任意三个元素 a、b、c必须满足cmp(a, a)为假cmp(a, b)和cmp(b, a)不能同时为真传递性成立。最常见的错误是写成x.weight y.weight用会在相等元素上返回真破坏反对称性STL 的很多算法在这种比较器下会做出未定义行为轻则结果错乱重则数组越界。还有一个机制上的细节值得说明。在 3.2 节的例子里两个Item如果weight相同它们就被视为等价。这时候next_permutation会把它们当成“同一个元素”不会生成它们互换位置的排列。如果你的业务需要区分它们label 不同就必须把 label 也加进比较逻辑里。这个行为经常让人困惑明明元素不一样为什么只输出了一半的排列答案就在这里。3.4 prev_permutation 的配合方式prev_permutation的用法和next_permutation完全对称唯一要变的是初始化方向。#include algorithm #include iostream #include vector int main() { std::vectorint a{1, 2, 3}; std::sort(a.begin(), a.end(), std::greaterint()); // 从最大开始 do { for (int x : a) std::cout x ; std::cout \n; } while (std::prev_permutation(a.begin(), a.end())); }这段会从3 2 1一直输出到1 2 3正好是字典序的逆序。我个人在实战中很少单独用prev_permutation更多是用next_permutation从头枚举。但它有两个场景特别合适题目要求按逆字典序输出用它比自己反转结果更省事。你在做双向搜索或者需要从“最大排列”往回压缩的场景比如求“字典序不大于 X 的最大排列”从最大的开始prev下去第一个满足条件的直接返回语义比正向枚举清晰。有一个坑需要提一下prev_permutation返回false时会把序列重排成最大排列而不是最小。这个绕回方向和next_permutation相反如果你在循环外还要继续使用这个序列别搞混了。3.5 只要第 k 个排列怎么办有些题目不需要枚举全部只要第 k 个k 从 1 开始或从 0 开始看题目定义。这时候有两种写法。第一种是循环推进 k 次代码最直接std::vectorint a{1, 2, 3, 4}; std::sort(a.begin(), a.end()); for (int i 0; i k; i) { std::next_permutation(a.begin(), a.end()); }这种写法在 k 比较小比如几千以内时完全够用代码可读性也最好。但如果 k 是几百万甚至上亿每次推进 O(n) 的代价累积起来就顶不住了。第二种是康托展开式的按位确定复杂度 O(n²)和 k 的大小无关。思路是从左往右每一位计算“把当前可用的最小元素放上去之后剩余元素还能组成多少个排列”如果这个数量小于 k就换下一个候选元素并减去相应的数量直到定位到正确的元素。这个思路实际上就是next_permutation的四步算法在更高维度上的推广理解其中一个另一个也就懂了。我实测下来的建议是k 在 10 万以内直接用循环推进代码短、不容易出错超过这个量级再考虑按位确定。别为了显得专业一上来就写复杂版本维护成本划不来。4. 常见问题与排查实录4.1 少算一个排列do-while 与 while 的差别这个问题的表现形式很隐蔽你跑完程序发现输出是 5 个而不是 6 个而且缺的正好是第一个。第一次遇到会怀疑是不是算法有 bug实际上就是循环结构写错了。// 错误写法漏掉初始排列 std::vectorint a{1, 2, 3}; std::sort(a.begin(), a.end()); while (std::next_permutation(a.begin(), a.end())) { // 输出 a } // 正确写法 do { // 输出 a } while (std::next_permutation(a.begin(), a.end()));判断准则很简单问自己当前这个初始序列算不算一个合法的排列。如果算就必须用do-while如果你确实只想跳过初始状态从下一个开始才用while。绝大多数情况下答案是前者。我踩过一次更绕的版本先用while循环发现有缺失改成do-while结果又变成了 6 个里有一个重复。追下去发现是因为我在循环体末尾手动又调了一次推进函数相当于一次循环走了两步。这种错误只能靠逐行 review工具帮不上忙。4.2 排序缺失导致结果残缺序列没排序是第二高频的问题。表现是输出结果看起来“有但是不全”或者干脆只输出一两个。回忆一下next_permutation的语义它只负责往前走不负责绕圈。初始序列是[2, 3, 1]的话它只能走到[3, 1, 2]、[3, 2, 1]然后结束。前面那些 231的排列全部被跳过了。排查方法很直接在进入循环前打印一次序列看它是不是升序。如果不是就是少了sort。对prev_permutation同理只不过它要求初始序列是降序。还有一个隐藏变种你对副本排了序但循环用的是原数组。比如函数参数传的是值你在函数里sort了一遍但外面调用方传进来的数组没变出现“排序了但没用上”的错觉。这种问题就得靠打印验证光看代码很难发现。4.3 比较器不满足严格弱序这个问题的表现很有欺骗性大部分测试用例都能过只在某几个特殊输入上出错比如有大量重复元素的时候。前面 3.3 节讲过的问题这里再说几个更隐蔽的。比较器里做了浮点运算。比如cmp(a, b) { return a.x / a.y b.x / b.y; }浮点误差会导致cmp(a,b)和cmp(b,a)可能同时为假也同时为真破坏传递性。比较器有副作用。比如在里面自增了一个计数器每次调用结果可能不同算法内部会陷入混乱。比较器捕获了外部可变状态。lambda 捕获的是引用而那个变量在排序过程中被改了后果和上一条一样。比较器本质上是偏序不是全序。比如比较二维点只比较 x 坐标当 x 相同时两个点等价next_permutation会把它们当成同一个元素。如果你没意识到这一点就会觉得“少了一半的排列”。这不是 bug是语义如此。排查技巧合法输入下不应该出现的问题就构造一组“比较器认为等价”的数据试试。如果结果突变基本就定位到了。4.4 字符串、浮点数、大小写std::string本身支持字典序比较所以next_permutation可以直接用。但如果你要的是不区分大小写的排列就得传自定义比较器并且注意排序和推进必须用同一个。auto icase [](char x, char y) { return std::tolower(static_castunsigned char(x)) std::tolower(static_castunsigned char(y)); }; std::sort(s.begin(), s.end(), icase); do { // 使用 s } while (std::next_permutation(s.begin(), s.end(), icase));注意std::tolower的参数必须转成unsigned char否则遇到负值字符在部分编码下会出现是未定义行为。这个细节很多人不知道写出来的代码在某些输入下会崩溃。浮点数用next_permutation是可行的但一定要用自定义比较器并且只能做“排序 枚举”绝对不能依赖精确相等做判断。我一般建议浮点场景先转成定点整数再枚举避免一切精度麻烦。4.5 性能与内存的实测经验我在一台普通笔记本上做了几组粗略测试数据只用于感受量级不代表精确基准。元素个数排列总数全部枚举耗时实际建议840320约 3 ms随便用103628800约 400 ms可用注意剪枝1139916800约 4.5 s需要剪枝或改算法12479001600约 55 s基本不可行13 以上60 亿以上不可接受必须换思路这张表的核心结论是10 个元素是一道门槛。超过这个量级先问自己是不是真的需要枚举全部排列大概率是可以用贪心、动态规划或者按位确定求解的。我在一次数据清洗脚本里就犯过这个错本来只需要找一个满足条件的排列结果写成了全枚举跑了几分钟才发现完全可以改成贪心构造一秒内出结果。内存方面next_permutation本身是 O(1)但要注意你输出结果时用的容器。如果每生成一个排列就push_back一份拷贝那内存会瞬间爆掉。正确做法是处理完立刻消费掉或者在处理函数内部完成逻辑不要积攒。4.6 问题速查表现象最可能原因快速验证修复输出少一个用了while而非do-while数一下总数改循环结构输出只有几个初始序列未排序循环前打印序列加sort升序枚举结果混乱比较器与排序时不一致比对两处比较器统一成同一个重复元素导致排列数不对比较器把不同元素判为等价检查比较字段加入区分字段程序在某些字符上崩溃tolower参数未转unsigned char换成宽字符输入试试加static_cast跑到一半极慢元素个数超过 11算一下阶乘换算法或加剪枝这张表我建议直接贴在笔记里遇到问题按行对照比重新读文档快得多。5. 变体扩展与工程取舍5.1 什么时候不该用这两个函数有两种情况我会明确避开它们。第一种是元素个数超过 11。前一张表已经说明白了13!是 62 亿任何“在合理时间内枚举完”的想法都不成立。这时候正确做法是先分析问题是不是真的需要全枚举绝大多数“全排列”题目的真实考点是剪枝、状态压缩或者数学构造串行枚举只是最朴素的版本。第二种是边生成边需要复杂判断。next_permutation只给你一个序列判断逻辑得自己在循环体里写。如果判断本身很重比如需要构建图、跑一次匹配那在循环里做会非常慢。更好的做法是把判断条件反过来用先分析出哪些排列必然不合法在推进前剪掉而不是全部生成后再过滤。还有一个小场景值得注意如果你只需要“固定前缀的所有排列”也就是前缀不变、只枚举后缀那可以对[prefix_end, end)这个子区间单独调用next_permutation不需要对整个序列操作。这个技巧在分组枚举里非常实用代码也干净。5.2 组合、子集等相邻变体next_permutation真正的用武之地不只有全排列。它最常用的一类变体是枚举组合通常配合一个0/1标记数组来做。#include algorithm #include iostream #include vector int main() { int n 5, k 3; std::vectorint mask(n, 0); std::fill(mask.end() - k, mask.end(), 1); // 先构造最小的组合标记 do { for (int i 0; i n; i) { if (mask[i]) std::cout i ; } std::cout \n; } while (std::next_permutation(mask.begin(), mask.end())); }这段枚举的是从 5 个里选 3 个的全部组合共 10 种。原理是把“选”记为 1、“不选”记为 0最小的排列是全 0 后跟全 1然后不断推进字典序每种 0/1 排布对应一个组合。由于 0 和 1 各有多个next_permutation会自动去重不需要额外处理。这个技巧我用了很多次比递归写组合简洁太多。想枚举“选 k 个元素的所有排列”也行在拿到组合之后再对选出来的元素做一次全排列两层循环嵌套逻辑清晰。另一个变体是可重集排列也就是输入里可能有重复元素。这个在 3.2 节讲过了直接排序去重即可不需要额外逻辑。唯一要注意的是内存和输出量——可重集的不同排列数可能仍然很大比如 20 个元素里 10 个 A、10 个 B组合数是 184756这个量级还能接受但如果是 30 个元素就该重新考虑了。5.3 一个可复用的小工具封装最后给一个我在项目里用的小封装把“排序 枚举 提前终止”三件事包起来调用方只需要写一个接收序列的 lambda。#include algorithm #include functional template class Container, class Handler void for_each_permutation(Container c, Handler handler) { std::sort(c.begin(), c.end()); do { if (!handler(c)) break; // 返回 false 表示提前终止 } while (std::next_permutation(c.begin(), c.end())); }handler返回bool表示“是否继续”这样就能在找到目标排列时立刻停下不用白白跑完剩下的全部。设计上其实有个小取舍handler接收的是Container调用方可以直接修改但会影响后续推进个人建议在业务代码里约定成只读或者传const Container。我这里用非 const 是为了保持灵活性比如某些场景需要在循环体里直接消费掉元素。这个封装的另一个好处是强制了排序这一步。工具层面把最容易忘记的东西固化下来比写文档提醒有效得多。我在团队里推行过类似的小工具新人踩“忘记排序”坑的概率肉眼可见地下降了。6. 我自己的使用体会用了这些年我对这两个函数最大的感受是它们看起来是“一个 API”实际上考的是你对字典序这个概念的理解深度。所有踩过的坑归根结底都源于脑子里那个模型不够清晰——不清楚它的起点在哪必须是最小排列、终点在哪碰到最大排列返回 false 并绕回、等价元素怎么处理视为同一个不生成互换、比较器的作用域必须和排序一致。我给自己的习惯是每次写这类代码前先在心里默念三件事先排序、用 do-while、比较器两处一致。这三条覆盖了九成以上的翻车场景。剩下那一成主要出现在自定义类型上尤其是比较字段选错导致的部分排列丢失这种情况只能靠构造边界数据去测没有捷径。另外分享一个我自己在用的小技巧调试全排列代码时把元素个数缩到 3 或 4手工写出期望的完整输出然后和程序结果逐行 diff。3!是 6 行4!是 24 行一眼就能比较完。比在几千行输出里找异常快得多也更容易定位到底是漏了、多了还是顺序错了。这个小办法帮我省掉的排查时间比任何工具都多。
