c++中std::next_permutation如何生成全排列 _c++ next_permutation全排列生成技巧-C++-PHP中文网

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

穿越時空

发布： 2025-10-20 15:25:01

原创

216人浏览过

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

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

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

工作原理简述

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

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

生成全排列的基本步骤

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

示例代码：

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

NameGPT名称生成器

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

查看详情

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

int main() {
vector<int> nums = {1, 2, 3};
sort(nums.begin(), nums.end()); // 确保起始为最小排列

do {
for (int n : nums) cout << n << " ";
cout << endl;
} while (next_permutation(nums.begin(), nums.end()));

return 0;
}

使用技巧与注意事项

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

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

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

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

以上就是c++++中std::next_permutation如何生成全排列 _c++ next_permutation全排列生成技巧的详细内容，更多请关注php中文网其它相关文章！