c++中std::next_permutation如何生成全排列 _c++ next_permutation全排列生成技巧

std::next_permutation通过字典序生成全排列，需先排序并循环调用直至返回false，可高效处理无重复或含重复元素的序列，适用于整数、字符串等可比较类型。

在C++中，std::next_permutation 是一个非常高效的算法工具，用于生成序列的下一个字典序排列。它定义在 <algorithm> 头文件中，能够按字典序递增的方式遍历所有可能的排列，非常适合用来生成全排列而无需递归。

工作原理简述

std::next_permutation 会重新排列当前序列，使其变为字典序中的下一个更大排列。如果当前已经是最大字典序（即完全降序），函数返回 false，并将序列重排为最小字典序（升序）；否则返回 true。

利用这一特性，只要从一个有序的初始序列开始（通常是升序），不断调用该函数，就能生成所有不重复的排列。

生成全排列的基本步骤

• 确保输入序列是可排序的容器（如 vector 或 array）
• 先对序列进行排序，得到字典序最小的排列
• 使用 do-while 循环输出当前排列并调用 next_permutation
• 循环直到 next_permutation 返回 false

示例代码：

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

return 0;
}

使用技巧与注意事项

想要高效正确地使用 next_permutation 生成全排列，注意以下几点：

NameGPT名称生成器

免费AI公司名称生成器，AI在线生成企业名称，注册公司名称起名大全。

0

查看详情

• 必须先排序：若初始状态不是最小字典序，会遗漏部分排列
• 支持任意可比较类型：不仅限于整数，字符串、自定义结构体（带比较运算符）也可用
• 自动去重：对于含重复元素的序列，它只会生成唯一的排列（前提是排序后调用）
• 时间复杂度合理：每个排列平均 O(n)，总复杂度 O(n! × n)，适合中小规模数据

例如处理重复元素：

vector<char> s = {‘a’, ‘a’, ‘b’};
sort(s.begin(), s.end());
do {
cout << string(s.begin(), s.end()) << endl;
} while (next_permutation(s.begin(), s.end()));

输出结果不会包含重复排列，系统自动跳过相同字典序的情况。

基本上就这些。掌握这个技巧后，写全排列问题可以简洁又高效，避免手动实现递归回溯的复杂逻辑。