企业官网建设流程全解析

next_permutation在很多人脑子里被归到了"全排列函数"这一类，好像调用一下就能吐出所有排列。实际上它压根不知道什么叫全排列，它只做一件很窄的事：把手里这段区间原地改成字典序上的下一个排列，然后用一个 bool 告诉你"改成功了没有"。明白了这一层，后面那些"必须先排序""重复元素会自动去重""返回 false 之后序列被偷偷改了"的坑，就都串成一条线了。这篇讲的就是这条线：两个函数的算法内核、使用前提、边界行为、手写实现，以及在字典序第 k 个排列、字符串重排这类真实场景里怎么用得不别扭。不管你是刚学 STL 的新手，还是刷题时被do-while和while绕晕过的老手，下面这些内容应该都能对上号。

1. 两个函数真正的职责边界：只认字典序，不认全排列

1.1 一个反直觉的结论：它不会"生成全排列"

先把最容易误解的地方说透。std::next_permutation(first, last)的语义是：把[first, last)这个区间重排成"按当前比较器排序的、字典序恰好大于当前序列的那个最小序列"。如果不存在更大的排列，它返回false，并且把区间重置为最小排列（对无比较器版本就是升序）。

注意这里的措辞——"恰好大于当前序列的那个最小序列"。它是一次局部改写的动作，不是一次枚举动作。所谓"用 next_permutation 求全排列"，其实是我们在外面套了一层循环，反复调用它，让序列沿着字典序一格一格往前走，走不动了循环结束。全排列是循环的产物，不是函数的产物。

这个区别看着像文字游戏，实际影响很大。因为它意味着：函数只保证"当前 → 下一个"这一步的正确性，枚举范围是否完整，责任在使用者身上。序列一开始是不是最小排列、循环写法有没有把初始状态漏掉、比较器和排序规则有没有对齐，这些都得自己兜住。我见过不止一个人觉得"我调了 next_permutation 啊，怎么只出来一半"，问题全部出在这三件事上。

1.2 字典序这个词到底指什么

字典序规则很朴素：从左到右逐位比较，第一个不同的位置上，元素小的那个序列更小；如果前缀完全相同，短的更小（对定长序列来说这一条用不上）。整数序列[1,2,3]的六个排列按字典序排开是：

next_permutation就是在这张表上往后跳一格。第 1 个位置上的"1 2 3"是全局最小的排列，第 6 个"3 2 1"是全局最大的排列。序列一开始必须站在表的第一格，才能保证循环把整张表走完——这就是"必须先排序"的真正原因，不是什么玄学约定。

这里还有个隐含前提：所有元素在比较器意义下必须是可全序比较的。int、char、std::string都没问题；自定义结构体如果只定义了==而没定义<，编译期就会报错，因为函数内部到处在用operator<。

1.3 返回值里藏着的边界语义

返回值是 bool，但它的含义经常被简化成"还有没有下一个"。更准确的说法是：

• 返回true：区间已经被改成下一个更大的排列，你可以放心用。
• 返回false：区间里已经没有更大的排列了，并且区间已经被改成了最小的那个排列。

第二条很多人不知道。这意味着你循环退出之后，手里那个容器不一定是最后那个"3 2 1"，而很可能已经悄悄变回"1 2 3"了。如果你在循环体里收集结果、循环外还想复用原容器，这个副作用会让你莫名其妙。

我一般会这样处理：如果退出后还需要原始数据，提前 copy 一份；如果只是想跑完就完事，那就不用管。另外，prev_permutation是完全镜像的逻辑——往前走一格，走不动了返回false并把区间重置为最大排列（降序）。

提示：false的副作用是"重置"，不是"保持不变"。这一点在调试阶段尤其容易看走眼。

2. 拆开标准库：一次交换加一次反转是怎么想出来的

2.1 从尾部往前找第一对升序

算法的第一步是：从右往左扫描，找到第一个满足a[i] < a[i+1]的下标i。为什么要从右往左？因为字典序的"变大"发生在最靠右的位置才最划算——改动越靠右，新序列与旧序列的差距越小，而我们要的就是"恰好大一点点的那个"。

反过来说，如果从右往左一路都是a[i] >= a[i+1]，说明整个序列是非递增的，也就是已经处于字典序的顶点，没有"下一个"了。这时直接整段反转成升序，返回false，正好对应上面说的重置语义。

找到的那个i很关键：i右边（不含i）的整段后缀一定是非递增的。这个性质是后面两步的地基，必须记住。

举个具体的：[1, 3, 5, 4, 2]。从右往左，4 >= 2、5 >= 4，都是非递增；到3 < 5停下，i = 1。后缀[5, 4, 2]确实是降序的。

2.2 为什么交换对象要选"大于它的最小元素"

第二步：在i的右侧找第一个满足a[j] > a[i]的元素j（从右往左找）。因为右侧是降序的，从右往左扫，第一个大于a[i]的元素，恰好就是右侧所有大于a[i]的元素里最小的那个。

为什么非要最小的？因为我们要让新序列"刚好比原来大一点"。位置i上放的元素决定了新序列的量级，放大一点就够了，放太大就跳过了中间那些排列。同理，位置i之前的前缀必须原封不动，任何改动都会让新序列偏离太远。

这一层其实是个贪心：在保证"新序列 > 原序列"的所有改法中，选字典序最小的那个。贪心的正确性依赖于后缀的有序性——有序才能用"从右往左扫第一个"直接拿到最小值，不用遍历比较。

用上面的例子：a[i] = 3，右侧[5, 4, 2]从右往左第一个大于 3 的是 4，j = 3。交换后得到[1, 4, 5, 3, 2]。

2.3 反转后缀而不是排序后缀

第三步：把i之后的后缀整段反转。

交换之后后缀[5, 3, 2]仍然是降序的（交换改变了i位置的元素，但后缀内部的相对大小关系没被破坏——严格说，交换进来的那个元素原本在降序段里，换出去的元素也满足相应关系，所以后缀依然是非递增的）。既然已经是降序，反转一次就变成升序，而升序正是这个后缀能取到的最小排列。用std::sort也能得到同样结果，但反转是 O(n)，排序是 O(n log n)，白白多花时间。

反转完成：[1, 4, 2, 3, 5]。这就是[1, 3, 5, 4, 2]的字典序下一个排列。可以自己在纸上验证一下中间没有别的排列了：以1开头、第二位是3的只有13542和13425两个，后者比前者小，说明13542已经是这一支的末尾；接下来跳到第二位是4的最小排列，就是14235。

2.4 复杂度与交换次数的实测账本

关键结论：

"最多 n/2 次交换"这个上界值得单独说一下。直观理解是：反转后缀的代价已经被算进去了，标准把反转也算作交换操作，而一次扫描反转最多做 n/2 次iter_swap。这也侧面说明实现里用的就是反转，而不是排序。

我做过一个粗略的计时，-O2编译，std::vector<int>，从1..n升序开始全量枚举：

这张表的意义在于给自己一个手感：n 超过 10 就别想着全量枚举了，无论算法多快，阶乘增长率会把一切优化碾平。后面讲"字典序第 k 个排列"的时候会说到，那时候的正确做法不是枚举，是直接算。

还有一点值得注意：next_permutation的迭代器要求是双向迭代器，不是随机访问迭代器。所以std::list理论上是能用的。但实际别这么干——链表的迭代器递增本身就慢，还要反复线性扫描，性能会比 vector 差一个数量级。用 vector、array、原生数组指针、std::string才是常规操作。

3. 手写一遍，才算真的理解那三步

3.1 一份可以直接对拍的实现

面试里被要求"手写 next_permutation"的概率挺高，因为这三个步骤短、有逻辑、能看出候选人是不是真的理解字典序。下面这份是用下标写的版本，不涉及模板，读起来最直白：

#include <vector> #include <algorithm> bool my_next_permutation(std::vector<int>& a) { int n = static_cast<int>(a.size()); if (n <= 1) return false; // 第一步：从右往左找第一对升序 int i = n - 2; while (i >= 0 && a[i] >= a[i + 1]) --i; // 整个序列非递增，说明已经是最大排列 if (i < 0) { std::reverse(a.begin(), a.end()); return false; } // 第二步：在右侧找大于 a[i] 的最小元素 int j = n - 1; while (a[j] <= a[i]) --j; // 第三步：交换 + 反转后缀 std::swap(a[i], a[j]); std::reverse(a.begin() + i + 1, a.end()); return true; }

两处比较符要盯紧：a[i] >= a[i + 1]用的是>=，a[j] <= a[i]用的是<=。如果写成>和<，遇到重复元素就会出错——比如[1, 1]，用>判断的话a[0] > a[1]不成立，会认为找到了升序对，然后去右侧找> a[0]的元素，一个都找不到，j直接越界。这个 bug 在只有互不相同元素的测试数据上完全看不出来，一上真实数据就崩。

3.2 拿标准库对拍

写完别急着信自己，对拍是最省事的验证方式。思路很土但有效：随机生成小规模的、带重复元素的数组，分别用标准库和自己写的版本跑完整轮枚举，把每一步的结果收集起来逐项比较。

#include <vector> #include <algorithm> #include <random> #include <cassert> #include <iostream> void check_once(std::vector<int> base) { std::sort(base.begin(), base.end()); std::vector<int> x = base, y = base; while (true) { bool ok1 = std::next_permutation(x.begin(), x.end()); bool ok2 = my_next_permutation(y); assert(ok1 == ok2); // 返回值必须一致 assert(x == y); // 状态必须一致（包括 false 后的重置） if (!ok1) break; } } int main() { std::mt19937 rng(42); for (int trial = 0; trial < 2000; ++trial) { int n = 1 + rng() % 7; std::vector<int> v(n); for (int& x : v) x = static_cast<int>(rng() % 4); // 故意制造重复 check_once(v); } std::cout << "all matched\n"; }

关键是对拍里也必须先sort，否则两边都从同一个非最小状态出发，只能覆盖到"从中间某处往后走"的路径，边界情况（false后的重置）根本测不到。这一步很多人懒得做，结果手写版看着没问题，一提交就 WA 在某个n=1的隐藏用例上。

3.3 prev_permutation 的镜像实现

prev_permutation把上面所有不等号反过来：

bool my_prev_permutation(std::vector<int>& a) { int n = static_cast<int>(a.size()); if (n <= 1) return false; int i = n - 2; while (i >= 0 && a[i] <= a[i + 1]) --i; // 找第一对降序 if (i < 0) { std::reverse(a.begin(), a.end()); // 重置为最大排列（降序） return false; } int j = n - 1; while (a[j] >= a[i]) --j; // 找小于 a[i] 的最大元素 std::swap(a[i], a[j]); std::reverse(a.begin() + i + 1, a.end()); return true; }

用prev_permutation枚举全排列时，起始序列必须是降序（也就是字典序最大的那个），然后一路往回走，走到底了整段反转成升序。这个"起始状态必须与行进方向匹配"的规律，是这两个函数最容易记混的地方，我在下一节会专门展开。

4. 那些让结果少一半的坑，我基本都踩过

4.1 忘排序：最经典也最致命的错误

先看一个能说明问题的例子。假设初始序列是[3, 1, 2]，直接进do-while：

• 第一轮输出3 1 2
• 调用一次，得到3 2 1
• 第二轮输出3 2 1
• 再调用，返回false，序列重置为1 2 3，循环结束

三个元素有六个排列，只输出了两个。原因很直接：[3,1,2]在字典序表里排在中间偏后的位置，往前走只剩一格了。排在它前面的四个排列，next_permutation永远不会回头去找。

所以枚举前必须先std::sort成升序。这一条几乎每个教程都会写，但新手经常犯的变体是："我在读数据的时候顺手排了"——结果排的是另一个数组，或者排完之后又做了别的操作把顺序打乱了。我自己的习惯是把sort和do-while写在紧挨着的两行，中间不插任何逻辑，从物理上杜绝这个问题。

prev_permutation同理，起始必须std::sort(a.begin(), a.end(), std::greater<>())排成降序。

4.2 do-while 还是 while，只差一个初始状态

这是另一个高频误区。对比两种写法：

// 写法 A：do-while，包含初始排列 std::sort(v.begin(), v.end()); do { process(v); } while (std::next_permutation(v.begin(), v.end())); // 写法 B：while，漏掉初始排列 std::sort(v.begin(), v.end()); while (std::next_permutation(v.begin(), v.end())) { process(v); }

写法 B 会少输出那个已经排好序的最小排列。对 n 个元素来说，少了 1/n! 的输出——当 n 比较小的时候这个比例相当可观（n=2 时少一半，n=3 时少六分之一），非常容易被当成"函数有 bug"。

反过来也有陷阱：如果你明确不想要"原序"这个排列（比如要求"在原串基础上做重排，输出必须与原串不同"），那就该用while，而且注意第一次调用之后原序已经被改掉了。这种需求下我一般先 copy 一份原始值留底，循环里再判断是否与原始值相同，逻辑更清晰，不用纠结用哪个循环。

还有一种写法是先用sort排好，然后手动process一次，再进while。效果和do-while等价，纯粹看个人习惯。

4.3 重复元素：它天然去重，但你得先排好

这是我个人认为next_permutation最有价值的一点。手写递归回溯做全排列，遇到重复元素时必须额外维护一个used数组或者用set去重，一不小心就重复输出。而next_permutation根本不给你重复的机会——因为它每一步都是"严格字典序下一个"，同一个序列在字典序表里只占一个格子，物理上不可能被输出两次。

验证一下：[1, 1, 2]，三个元素理论上 6 种排列，去重后只有 3 种。

• 排序后1 1 2，输出
• 下一个：i扫到a[1]=1 < a[2]=2，i=1；j找>1的，j=2；交换 →1 2 1；反转后缀（只有一位）→1 2 1，输出
• 下一个：a[1]=2 >= a[2]=1，i=0；a[0]=1 < a[1]=2，停；j从右找>1的，j=1（a[1]=2）；交换 →2 1 1，反转 →2 1 1，输出
• 下一个：非递增，返回false，重置为1 1 2

正好三个，一个不多一个不少。这就是它比手写回溯省心的地方。

但前提还是那个：必须先排序。[2, 1, 1]直接开跑，只能拿到它自己和它后面的，前面两个全丢。而且重复元素的情况下，"排序"这个动作本身还顺便把相同元素聚到了一起，这对算法正确性是必需的——如果相同元素散落各处，那"后缀非递增"这个不变式就会被破坏，后续的贪心选最小元素也会失效。

4.4 自定义比较器：类型、浮点和严格弱序

带比较器的重载next_permutation(first, last, comp)里，comp(a, b)表示"a 应该排在 b 前面"。用自定义比较器时，排序也必须用同一个comp，否则起始状态不是该比较器下的最小排列，枚举范围又会缺。

// 按绝对值升序枚举 auto cmp = [](int a, int b) { return std::abs(a) < std::abs(b); }; std::sort(v.begin(), v.end(), cmp); do { process(v); } while (std::next_permutation(v.begin(), v.end(), cmp));

这里有个更隐蔽的雷：comp必须构成严格弱序。通俗说就是不能出现comp(a,b)和comp(b,a)同时为真，也不能出现comp(a,a)为真。如果违反，标准库的行为是未定义——不是报错，是"跑出什么结果都有可能"，可能死循环，可能数组越界。

浮点数就很危险。double里有 NaN，任何和 NaN 的比较都返回 false，直接破坏严格弱序；即使没有 NaN，精度误差也可能让两个"理论上相等"的值在实践中一会儿大一会儿小，导致next_permutation认为还有"下一个"却怎么也走不到尽头。我的建议很干脆：涉及浮点的全排列，先把浮点转成整数（乘个 10 的幂取整），或者干脆别用 next_permutation。

结构体作为元素时，需要提供一个明确的、无歧义的<。如果结构体里有多个字段，最好按一个确定的全序字段组合来定义比较，别让两个不同对象"既不大于也不小于"，那样字典序表里会出现并列，算法的行为就不符合直觉了。

4.5 空区间、单元素和递减序列

几个必须覆盖的边界：

单元素那一行值得单拎出来。用do-while处理n=1时，循环体会执行一次，然后调用返回false退出，输出一个排列——这是对的，一个元素确实只有一种排列。但如果题目语境是"两个及以上元素的重排"，n=1就该特殊处理，否则可能输出一个不期望的结果。我写这类代码时习惯在函数开头加一句if (v.size() <= 1) return ...;提前返回，比在循环里纠结清爽得多。

5. 落到具体题目上：从第 k 个排列到字符串重排

5.1 字典序第 k 个排列：枚举不是最优解

这是一道很经典的题：给定 n 和一个整数 k，求1..n的字典序第 k 个排列。

最直接的想法是排好序，然后调k-1次next_permutation。这能过，但复杂度是 O(k·n)，k 最大可能到 n!，n=9 的时候 k 能到 36 万，勉强；n=12 就彻底不行了。

更合理的做法是逐位确定，用阶乘数系（康托展开的逆运算）。思路是：第一位放哪个数字，取决于后面n-1个位置能排出多少种组合，也就是(n-1)!种。把 k 减一之后，k / (n-1)!就是第一位在候选列表里的下标，k % (n-1)!是剩下的序号，然后对n-1递归。

std::string getPermutation(int n, int k) { std::vector<int> fact(n + 1, 1); for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i; std::vector<char> pool; for (int i = 1; i <= n; ++i) pool.push_back('0' + i); --k; // 转成 0-based std::string res; for (int i = n; i >= 1; --i) { int idx = k / fact[i - 1]; k %= fact[i - 1]; res.push_back(pool[idx]); pool.erase(pool.begin() + idx); } return res; }

复杂度 O(n²)（erase是线性的），比枚举的 O(k·n) 低了不知道多少个数量级。这里的取舍很清楚：当你要的是"第 k 个"而不是"全部"时，就别用枚举。next_permutation适合的场景是枚举总量可控（n ≤ 10 左右）或者需要在枚举过程中做判断的情况。

5.2 字符串重排：把std::string当容器用

std::string的迭代器是随机访问的，next_permutation直接就能用，这是它比很多语言方便的地方。leetcode 上有道"字符串的排列"，要求输出某个字符串所有不重复的排列，典型做法就是：

std::vector<std::string> permutation(std::string s) { std::vector<std::string> res; std::sort(s.begin(), s.end()); // 关键：保证从最小排列开始，顺便完成去重 do { res.push_back(s); } while (std::next_permutation(s.begin(), s.end())); return res; }

三行核心代码，去重、排序、枚举全齐了。手写回溯的话，光是"同一层相同字符跳过"那个判断就够写五行，还容易写错。

有个细节值得注意：std::sort对std::string是按字符的 ASCII 值排的，大写字母（65–90）全部排在小写字母（97–122）前面。所以输入如果是混合大小写，输出顺序会看着有点怪，但那是字典序的正确结果，不是 bug。真需要按字母表顺序（忽略大小写）排，就得传自定义比较器，而且循环里的next_permutation也得传同一个。

5.3 配合剪枝：枚举只是一种遍历骨架

纯枚举全排列的场景其实不多，更多时候是"枚举 + 判断"。比如给一组数字和一个目标值，问能不能在它们之间插入+或-使表达式成立；又比如给几个数字和一个目标，问怎么排列能让前一个数整除后一个数。

这类题用next_permutation的好处是，它把"枚举顺序"这件事彻底外包出去了，你只需要在循环体里写判断逻辑，不用操心递归状态、回溯还原、访问标记这些杂事。代码结构非常平：

std::sort(nums.begin(), nums.end()); do { if (check(nums)) { // 找到解，按题意决定是立即返回还是继续收集 } } while (std::next_permutation(nums.begin(), nums.end()));

代价是没法在枚举途中剪枝。递归回溯可以在搜索到一半发现"这条分支已经不可能成立"时提前回头，而next_permutation只能老老实实走完全部 n! 个状态。所以判断标准是这样的：

• 判断条件依赖整个排列 → 用next_permutation，剪枝没意义。
• 判断可以增量地做（前缀一旦不满足就可以放弃） → 用递归回溯，配剪枝会快很多。

我个人的经验是，凡是被归类为"简单题"和"中等题"的排列枚举，几乎都是第一种情况，next_permutation一把梭就完了。硬上回溯反而容易在去重上翻车。

5.4 和递归回溯的取舍清单

把两者的对比整理成表，用的时候照着挑：

最后一行那个"中途修改元素"值得展开一句。因为next_permutation的正确性建立在"当前序列是有序区间上的一个排列"这个前提上，如果你在循环体里改了元素值（不是交换位置，是改变值本身），那下一个状态就不一定是字典序下一个了，后续所有生成的排列都不可信。真需要改，就在循环体里对一份副本操作，别动原容器。

6. 几个容易被忽略的工程习惯

写到最后，说几个我用了很久才养成的小习惯，都是吃过亏之后改的。

第一，把sort和循环绑成一对写。不管多确定数据已经有序，都补一句std::sort。排一个已经有序的数组代价是 O(n)，可以忽略；但漏排一次的调试成本可能是半小时。

第二，区分"想要原序"和"不想要原序"。这个判断在写代码之前就要想清楚，而不是写完do-while之后发现多输出了一个再去改。我一般会在变量名上做区分，比如all_permutations和strictly_later_permutations，逼自己在命名时就明确语义。

第三，n 的规模先算一遍阶乘。写之前先10! = 3628800、11! = 39916800心里过一遍，超过千万级别就该换算法了，别等提交之后 TLE 再回头想。这条对涉及时间限制的题目尤其重要。

第四，prev_permutation别忘了配套的降序排序。我见过最多的一类错误是：想生成降序的排列序列，sort写成了默认升序，结果只输出一个元素就结束了。正确写法是std::sort(v.begin(), v.end(), std::greater<int>())或者直接std::sort(v.rbegin(), v.rend())。

第五，对拍比读代码快。手写实现的时候，写完之后不要盯着看，直接跑一组随机对拍。上面那个对拍模板我基本是复制粘贴复用的，改一下元素类型就能用，比人眼审查靠谱得多。

还有一个挺实用的小技巧：如果只是想知道某个序列在全排列表里的序号（或者反过来，从序号反推序列），用康托展开比调next_permutation快得多，前者 O(n²)，后者最坏 O(n!·n)。这两个函数的定位其实很明确——它们是遍历工具，不是索引工具。想清楚这一点，用起来就不会拧巴了。