C++全排列：next_permutation与prev_permutation

打开编辑器写全排列这件事我从学C的第一年折腾到现在。最早是拿着一道“输出1到n所有排列”的题吭哧吭哧写了几十行DFS加used数组递归回溯调了半天输出顺序还跟题目要求的字典序对不上。后来有人甩给我一句next_permutation两个循环变量、一个do-while问题当场没了。那一刻的感觉很直接STL里早就把这活儿干完了我自己在那造什么轮子。这篇就聊聊C标准库里的next_permutation和prev_permutation这对兄弟函数——它们是什么、底层怎么算的、有哪些必须注意的前置条件、在真实项目里怎么用才不出岔子。不管你是刚接触STL的新手还是写过几年代码但一直把这俩函数当黑盒用的老手下面这些内容应该都能让你少踩几个坑。1. 从一道全排列题说起这两个函数到底解决了什么问题1.1 手写DFS全排列为什么让人头疼先说说手写方案的问题不然后面讲STL的优势就没参照物。用DFS加回溯生成全排列核心代码大概是这样的维护一个used数组标记元素是否被选过递归深度到达序列长度时输出当前路径然后回溯撤销标记。逻辑本身不难但实际操作起来有几个绕不开的痛点。第一是输出顺序。DFS天然按“选第一个元素、选第二个元素”的路径顺序生成结果如果输入序列本身是乱序的输出顺序就不是字典序。题目一旦要求“按字典序输出”或者“求第k个排列”你就得额外排序或者用别的策略光靠DFS那套框架处理起来很别扭。第二是重复元素。输入[1,1,2]的时候DFS会老老实实生成6个结果其中三个是重复的。想输出不重复的排列常规做法是在同一层递归里加一个“本层已选元素集合”去重这段逻辑写起来不难但很容易漏尤其是元素类型换成字符串或者自定义结构体之后。第三是内存与常数。每次递归路径都要拷贝一份当前排列元素多了以后内存分配和拷贝开销很可观。虽然可以改成原地交换但原地交换又会影响输出顺序两头不讨好。我见过不少同学的代码DFS写了七八十行注释一堆跑出来的结果还得手动去重排序。这种场景下标准库提供的方案就显得格外干净。1.2 next_permutation与prev_permutation的定位与适用人群next_permutation的作用一句话概括把区间[first, last)原地重排成“按当前比较规则的下一个字典序排列”如果已经不存在下一个就重置成最小的那个排列并返回false。prev_permutation完全对称找的是上一个。这两个函数的定位很清晰需要按字典序、有序、不重复地枚举一个序列的所有排列时它们是首选工具。典型场景包括全排列输出、字典序第k个排列、下一个更大排列这类算法题也包括一些工程里的枚举搜索——比如小规模参数组合的穷举、测试用例的排列覆盖、字符串异位词的字典序遍历。适合谁看如果你正在刷算法题、准备面试这两个函数基本是必会项如果你在写业务代码时遇到过“枚举所有可能组合再筛选”的需求它们同样能省掉一大段递归代码。但要注意一点这两个函数只负责“走一步”不负责“从头开始”前置的排序步骤如果漏了结果就是残缺的这个坑后面会专门讲。2. 底层逻辑拆解字典序的“下一个”是怎么算出来的2.1 字典序的严格定义理解算法之前得先把“字典序”这个概念钉死。给定两个长度相同的序列从左往右逐位比较第一个不相同的位置上元素较小的那个序列就排在前面。如果所有位置都相同两个序列相等。这个定义跟查字典的规则一模一样所以叫字典序。放到全排列的语境里所有排列按这个规则排成一条链next_permutation就是沿着链往后走一步。举例来说[1,2,3]的六个排列按字典序是1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1next_permutation对第一行操作得到第二行对最后一行操作返回false并把序列重置回第一行。这个“重置”行为很关键它意味着你可以用返回值控制循环而不需要额外判断边界。2.2 找下一个排列的三步走算法STL的实现思路是原地交换加局部反转分三步。假设当前序列是a长度为 n。第一步从右往左找第一个“升序对”。找满足a[i] a[i1]的最大下标 i。如果整个序列从右往左看是单调不增的也就是最大的排列这一步会找不到直接进入收尾逻辑把整个区间反转返回false。第二步从右往左找第一个比 a[i] 大的元素。记下标为 j满足a[j] a[i]。因为第一步已经保证了a[i1]到a[n-1]是单调不增的所以从右往左第一个大于a[i]的元素一定是右侧所有比a[i]大的元素里最小的那个。这个性质是算法正确性的核心。第三步交换 a[i] 和 a[j]然后反转 a[i1] 到末尾。交换之后右侧区间仍然是单调不增的这个可以自己推一下反转之后变成单调不减正好是“以 a[i] 位置新元素开头的最小排列”。拿[1,3,2]走一遍第一步从右往左找3 2不满足升序1 3满足所以 i0。第二步从右往左找第一个大于a[0]1的是a[2]2j2。交换后得到[2,3,1]反转[3,1]得到[2,1,3]。验证一下[1,3,2]之后确实是[2,1,3]正确。2.3 prev_permutation的镜像逻辑prev_permutation把上面三步里的不等号全部翻过来找第一个a[i] a[i1]的下标再从右往左找第一个小于a[i]的元素交换最后反转右侧区间。找不到的时候说明当前是最小排列反转整个区间变成最大排列返回false。这个对称性意味着两个函数的实现代码几乎可以复制粘贴只改比较方向。理解其中一个另一个自然就通了。复杂度方面整个操作至多进行 n/2 次交换和若干次比较时间是 O(n)并且是原地操作不需要额外空间。这个常数和内存表现是DFS方案比不了的。3. 函数原型与参数细节那些文档里一笔带过的地方3.1 标准签名与返回值语义两个函数在algorithm头文件里都有两个重载版本templateclass BidirIt bool next_permutation(BidirIt first, BidirIt last); templateclass BidirIt, class Compare bool next_permutation(BidirIt first, BidirIt last, Compare comp); templateclass BidirIt bool prev_permutation(BidirIt first, BidirIt last); templateclass BidirIt, class Compare bool prev_permutation(BidirIt first, BidirIt last, Compare comp);返回值bool的含义需要说清楚返回true表示“成功找到了下一个排列区间已被重排”返回false表示“当前已经是最后一个或第一个排列不存在下一个了区间已被重置到另一个极端”。这个双语义设计很容易被误解成“操作失败什么都没变”实际上序列是变了的。从C20开始这两个函数被标记为constexpr可以在编译期求值。如果你在写模板元编程或者需要编译期常量排列的场景这个特性挺有用。迭代器要求是BidirectionalIterator意味着std::list、std::vector、std::string、原生数组都能用但单向迭代器比如forward_list不行。3.2 迭代器范围、比较器与复杂度区间遵循C一贯的左闭右开约定first可达last不可达。传参的时候有两个细节要注意一是first和last必须来自同一个容器混用不同容器的迭代器是未定义行为二是别在调用时对同一个容器同时做修改操作虽然这两个函数本身是原地修改但如果你写成next_permutation(v.begin(), v.end())之后立刻又读v.begin()那个迭代器在部分容器上可能失效。带比较器的版本允许你自定义“字典序”。比如想让排列按绝对值大小排序或者按字符串长度优先都可以传入一个二元谓词。但这里有个硬性要求比较器必须满足严格弱序也就是对任意元素 a、bcomp(a,b)和comp(b,a)不能同时为真且传递性要成立。比较器写错了函数的行为是未定义的不一定是崩溃更可能是悄悄产出错误结果这种bug排查起来非常痛苦。复杂度方面单次调用至多(last - first) / 2次交换整体 O(n)。但要注意枚举全部排列的总代价是 O(n! * n)因为要调用 n! 次。n 稍微大一点这个数字就爆炸了20! 约等于 2.4×10^18实际能枚举的规模通常在 10 到 12 以内。3.3 必须排序这个前置条件的前因后果这是使用这两个函数最容易翻车的地方单独拎出来讲。next_permutation不会帮你把序列排好序再开始它只做一件事从当前状态往后走一步。所以如果初始序列不是最小的那个排列你得到的只是“从当前位置开始的后缀排列”前面那些排列全丢了。举个具体例子。输入[2,1,3]直接循环调用next_permutation输出是2 1 3 2 3 1 3 1 2 3 2 1只有四个而[1,2,3]的全排列有六个1 2 3和1 3 2这两个被跳过了。原因很简单它们排在2 1 3前面。正确的模板是先用std::sort升序排序再进入 do-while 循环。用prev_permutation枚举全部排列则要降序排序。这个“先排序”的步骤不是可选项是必选项而且排序用的比较器必须和后面传给next_permutation的比较器保持一致否则排序结果不满足算法要求输出同样是残缺的。提示如果只需要求“当前排列之后的下一个”不需要枚举全部那当然不用排序。判断标准很简单——你要的是完整枚举还是单步推进。4. 实操从字符串全排列到去重输出的完整流程4.1 最基础的do-while循环模板标准写法长这样我建议直接背下来#include algorithm #include iostream #include string int main() { std::string s bca; std::sort(s.begin(), s.end()); do { std::cout s \n; } while (std::next_permutation(s.begin(), s.end())); return 0; }输出是abc、acb、bac、bca、cab、cba六个字典序排列齐全。这里必须用do-while而不是while。原因在于第一次进入循环时当前序列本身就是一个有效排列需要先输出再判断有没有下一个。如果写成while (next_permutation(...))第一次调用就已经把序列推进到第二个排列了第一个排列被跳过。这个细节新手极容易搞错我见过不止一次有人困惑“为什么少了第一个结果”。std::string能直接用是因为它满足双向迭代器要求字符按 ASCII 码比较。对于原生数组写成next_permutation(arr, arr n)也可以指针本身就是合法的迭代器。4.2 处理重复元素的正确姿势含重复元素的序列next_permutation的行为是只生成不重复的排列每个唯一排列恰好出现一次。这是由算法本身决定的因为它在比较元素值重复元素在交换后不会产生新的字典序位置。输入[1,1,2]排序后枚举的结果是1 1 2、1 2 1、2 1 1三个符合预期。也就是说用next_permutation做全排列天然自带去重不需要你额外写unique或者集合去重。这一点比DFS方案省心太多。但这里藏着一个反直觉的点重复元素不会导致结果翻倍但如果你在循环里对结果做额外处理比如把排列存进std::set再去重那属于画蛇添足性能白白浪费。另外如果序列里有自定义类型比较器必须能正确处理“相等”的情况返回false而不是随便给个顺序否则去重逻辑会失效。4.3 逆序枚举与双向遍历需要从大到小枚举排列时用prev_permutation配合降序排序std::vectorint v {1, 2, 3}; std::sort(v.begin(), v.end(), std::greaterint()); do { // 处理当前排列 } while (std::prev_permutation(v.begin(), v.end()));还有一个更实用的技巧从某个中间排列出发同时向两边扩展。比如你需要以某个特定排列为中心列出它前后各若干个排列可以这样写先输出当前序列然后复制一份原序列用next_permutation向后走另一份用prev_permutation向前走。注意两份副本都要在排序后的完整排列空间内才安全否则走几步就撞到边界返回false了。这个双向遍历在“求某个排列附近的最优解”这类问题里很有用比如某些约束满足问题从启发式解出发做局部搜索相邻排列就是天然的邻域。5. 进阶用法字典序第k个、自定义比较、与其它算法组合5.1 求字典序第k个排列的两种思路最直接的办法是排序后循环调用next_permutationk-1 次复杂度 O(k*n)。k 小的时候完全够用代码三行。但 k 一旦到百万级别这个方案就废了因为每次调用都要扫一遍序列。更好的办法是用数学方法直接定位。核心思路是阶乘进制第 i 位从0开始的字符由剩余字符数 (n-1-i)! 决定。以n4, k9k从1开始计数为例先k-18剩余字符[1,2,3,4]。第一位索引是8 / 3! 8/6 1取第二个字符2余数8%62第二位索引2 / 2! 1剩余[1,3,4]里取第二个3余数2%20第三位索引0 / 1! 0取1最后剩4。结果2314。这个方法的复杂度是 O(n^2)主要是每次删除元素用树状数组优化可以到 O(n log n)。它和next_permutation是互补关系k 小用迭代k 大用数学。我一般会先估一下 k 的量级再选方案别上来就写复杂的。5.2 自定义比较器的坑带比较器的版本给了很大灵活性。比如按元素的绝对值排序std::vectorint v {-1, 2, -3}; auto cmp [](int a, int b) { return std::abs(a) std::abs(b); }; std::sort(v.begin(), v.end(), cmp); do { // ... } while (std::next_permutation(v.begin(), v.end(), cmp));但这里有几个坑必须提前说清楚。第一比较器必须对“相等”的元素返回false也就是cmp(a,a)必须是false否则严格弱序被破坏。绝对值比较里-2和2是“相等”的比较器对它们互相都返回false这是对的next_permutation会把它们当成重复元素处理不会产生两份排列。第二如果比较器里包含状态比如捕获了外部变量要确保在整个枚举过程中状态不变否则排序和枚举用的规则不一致结果必然错乱。第三浮点数比较器要特别小心 NaN 和精度问题a b在浮点上不满足严格弱序的所有性质用之前最好先做规整。5.3 与sort、reverse、unique的组合技几个常用的组合模式实践中出现频率很高。模式一排序加枚举。最基础前面反复提过不再展开。模式二枚举加剪枝。如果只需要满足某个条件的排列在循环体内判断不满足就continue。注意不能用break提前退出除非你确定后续排列都不可能满足——字典序的排列没有单调性break会漏解。模式三与is_permutation配合验证。判断两个序列是否互为排列std::is_permutation是专门干这个的内部也是排序后比较的思路但接口更直接。写测试用例的时候我会用它来校验枚举结果是否完整。模式四与reverse配合求“循环下一个”。有时候需要的是循环排列而不是线性排列也就是最后一个排列的下一个回到第一个。next_permutation返回false时已经帮你重置了直接用返回值当循环条件就行不需要手动reverse。6. 常见问题与排查技巧实录6.1 忘记排序导致漏解这是最高频的问题没有之一。表现是输出结果比预期少而且少的总是字典序靠前的那几个。排查方法很简单把第一个输出打出来跟理论上的最小排列比一比不一致就说明排序漏了。还有一种隐蔽情况排序了但排序和枚举用的比较器不一致。比如排序用默认的枚举传了自定义比较器这时候排序结果不满足枚举算法的前置条件输出同样残缺。我的习惯是把比较器定义成一个具名变量排序和枚举共用同一个从源头上避免不一致。6.2 do-while与while的误用前面提过while会跳过第一个排列。但还有另一种误用在do-while里对序列做了修改导致下一轮的状态不是上一轮枚举的结果。比如循环体内对序列做了sort或者交换下一轮next_permutation就基于一个完全不同的状态走了结果必然错乱。循环体内只读不写这条规则要守住。6.3 重复元素相关的三个误解第一个误解是“有重复元素就要先去重”。不需要next_permutation自己处理了。第二个误解是“重复元素会导致返回false提前”。不会它只在真正没有下一个唯一排列时才返回false。第三个误解是“重复元素的排列数量是 n!”。实际数量是 n! 除以各重复元素出现次数的阶乘比如[1,1,2]是 3!/2! 3跟实测一致。6.4 性能与内存的实测对比我做过一个粗略的对比测试n9 的全排列362880 个用next_permutation枚举并累加校验和的耗时大约在毫秒级而DFS加vector拷贝的方案要慢一个数量级主要开销在递归栈和容器拷贝上。改成DFS原地交换后差距缩小但仍然比STL版本慢因为STL版本没有函数调用开销且访问模式对缓存友好。内存方面next_permutation是纯原地操作额外空间 O(1)。DFS方案如果保存路径空间是 O(n) 加上递归栈。如果结果需要全部存储两者都逃不掉 O(n! * n) 的结果内存这部分才是真正的瓶颈。6.5 常见问题速查表现象可能原因排查方法解决方式结果数量比 n! 少初始序列未排序打印第一个结果对比最小排列循环前加std::sort少了第一个排列while代替do-while检查循环结构改成do-while排序和枚举结果不一致两处比较器不同对比两处传入的谓词共用同一个具名比较器含重复元素结果翻倍手动额外做了排列检查是否嵌套了DFS移除多余逻辑返回false后序列变了误解返回值语义打印重置后的序列理解回绕行为按需使用编译报错找不到函数未包含algorithm检查头文件补上#include algorithm自定义类型编译失败缺少可比较性看错误信息是否涉及operator提供比较器或重载运算符大 n 时程序卡死排列数量爆炸估算 n! 大小换数学方法或加剪枝7. 手写实现与STL对比什么时候值得自己写7.1 一份可以直接对照的手写版本把算法手写一遍是理解这两个函数最快的路径。下面这份实现和标准库逻辑一致templateclass BidirIt bool my_next_permutation(BidirIt first, BidirIt last) { if (first last) return false; BidirIt i last; if (first --i) return false; while (true) { BidirIt i1 i; if (*--i *i1) { BidirIt i2 last; while (!(*i *--i2)) {} std::iter_swap(i, i2); std::reverse(i1, last); return true; } if (i first) { std::reverse(first, last); return false; } } }这段代码里有两个边界处理值得注意空区间和单元素区间直接返回false因为不存在“下一个”的概念找不到升序对时反转整个区间并返回false对应回绕行为。手写一遍之后你会对“为什么右侧区间一定是单调不增”这个性质有更直观的感受。7.2 性能实测与场景选择什么情况下值得自己写我的判断标准有三个。需要部分枚举时。如果只要前几百个排列手写一个带提前终止的版本可以省掉next_permutation内部的完整扫描但省的这点开销通常可以忽略除非在极紧的性能循环里。实测下来标准库版本因为编译器优化和内联往往比你手写的还快。需要定制“下一个”的语义时。比如某些组合优化问题里“下一个”不是字典序而是某种自定义邻域。这时候标准库帮不上忙只能自己写。但要清楚自定义语义之后就没有字典序保证去重、完备性这些性质都要重新论证。教学或调试场景。想搞清楚算法每一步在干什么手写版可以加打印比单步调试标准库实现直观得多。这种情况下手写的价值在理解不在性能。除此之外的场景我建议无脑用标准库。它经过了几十年的测试和优化边界处理比你临时写的版本可靠得多。真正需要关注的是前置条件有没有满足、比较器有没有写对、循环结构有没有搞错这三件事做对了标准库版本就是最省心的选择。我在实际项目里用这两个函数最多的场景其实是小规模参数组合的穷举校验——比如验证某个查找逻辑在所有输入排列下是否一致。这类场景的 n 通常不超过 8next_permutation加上do-while两行代码就能覆盖比搭一套递归框架干净太多。唯一一次被坑是早期忘了排序跑了一下午都在纳闷结果怎么只有理论值的一半后来把第一个输出打出来才反应过来。这种错误犯过一次后面就再也不会忘了。