17370845950

next_permutation必须先排序，因为它是字典序游标而非全排列生成器；未排序时会跳过前面排列，如{3,1,2}直接调用得{3,2,1}，遗漏{1,2,3}等；排序后循环调用才能完整遍历且自动去重。

next_permutation 为什么必须先排序？

因为 next_per

mutation 不生成“所有可能排列”，它只按字典序生成「下一个」排列。如果初始序列不是最小字典序，调用一次就可能跳过前面大量排列。比如数组 {3,1,2} 直接调用 next_permutation，得到的是 {3,2,1}，而 {1,2,3}、{1,3,2}、{2,1,3} 等全被跳过。

正确做法是：先用 sort 排成升序，再循环调用 next_permutation，直到返回 false。

• 升序是字典序起点，保证不遗漏
• 降序是终点，此时 next_permutation 返回 false 并将容器重置为升序（注意：这是副作用，别依赖）
• 含重复元素时，仍需先 sort，但结果会自动去重——它只生成「字典序严格递增」的下一个排列，重复值相邻时不会重复生成相同排列

next_permutation 的参数和返回值含义

next_permutation 是 中的函数模板，签名是：

bool next_permutation(Iterator first, Iterator last);

它操作的是 [first, last) 左闭右开区间，要求迭代器支持双向遍历（vector、string、普通数组指针都满足）。

• 返回 true 表示成功生成下一个排列，原容器内容已被修改
• 返回 false 表示当前已是字典序最大排列（如 {3,2,1}），此时容器被重排为最小排列（{1,2,3}）
• 不接受自定义比较函数也能工作，但若要用自定义序（如降序排列），必须传第三个参数：next_permutation(v.begin(), v.end(), greater())

含重复元素时怎么避免输出重复排列？

标准 next_permutation 本身已处理重复：它基于“找最长非升序后缀 + 交换 + 翻转”的算法，天然跳过字典序相同的连续排列。所以只要输入已排序，输出就是无重复的全排列集合。

验证示例：对 {1,1,2} 排序后调用：

sort(v.begin(), v.end()); // {1,1,2}
do {
    // 输出 v
} while (next_permutation(v.begin(), v.end()));

实际输出只有 3 行：{1,1,2}、{1,2,1}、{2,1,1} —— 没有重复。

• 不要手动加 set 去重，性能差且没必要
• 如果输入未排序（如 {1,2,1}），第一次调用前必须 sort，否则行为不可预测
• 想保留原始顺序并枚举所有「位置排列」（含重复），那就不能用 next_permutation，得改用回溯

string 和 vector 调用方式完全一样吗？

是的，接口一致，但要注意 string 的字符类型是 char，字典序按 ASCII 值比较；而 vector 按数值比较。这点在混合数字字符时容易出错。

例如：

string s = "123";
next_permutation(s.begin(), s.end()); // 正确，得到 "132"

但：

vector v = {'1','2','3'};
next_permutation(v.begin(), v.end()); // 行为相同，因为 char 可比较

• vector 也能用，按字符串字典序排列（不是按长度）
• 数组指针也支持：int a[] = {1,2,3}; next_permutation(a, a+3);
• 不支持 list（因无随机访问），但可用 vector 中转

C++ 标准库的 next_permutation 看似简单，真正踩坑多在「忘记排序」「误判返回值语义」「拿它处理未排序或非线性容器」这三处。它不是黑盒生成器，而是字典序游标——理解这一点，比记住语法更重要。