C++如何实现全排列算法-C++-PHP中文网

std::next_permutation必须先排序，因为它只生成当前序列的字典序下一个排列，不保证从最小排列开始；若初始非升序（如{3,1,2}），会跳过{1,2,3}等前置排列。

c++如何实现全排列算法

std::next_permutation 为什么必须先排序？

因为 std::next_permutation 是按字典序生成「下一个」排列，它不负责从头开始枚举所有可能——它只在当前序列基础上推进一步。如果初始序列不是最小字典序（比如 {3,1,2}），调用一次 next_permutation 会跳过 {1,2,3}、{1,3,2} 等前面的排列。

实操建议：

务必先对容器调用 std::sort，确保起始状态为升序
用 do-while 循环，而非 while，避免漏掉原始排序后的第一个排列
注意：该函数修改原容器，如需保留原始顺序，应先拷贝

vector<int> v = {3, 1, 2};
sort(v.begin(), v.end()); // → {1,2,3}
do {
    // 处理当前排列
} while (next_permutation(v.begin(), v.end()));
</int>

递归实现全排列时重复元素怎么去重？

当输入含重复数字（如 {1,1,2}），朴素递归会输出 6 个结果，但实际不同排列只有 3 个：{1,1,2}、{1,2,1}、{2,1,1}。关键不在结果后去重，而在搜索过程中剪枝。

实操建议：

先排序，使相同元素相邻
递归中加判断：if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) —— 这表示前一个相同数没被用过，说明它属于上一层回溯，当前分支应跳过
用 vector<bool></bool> 标记是否已选，比用 set 查重更高效且稳定

用 std::next_permutation 处理字符串或自定义类型？

std::next_permutation 依赖 比较运算符，对 <code>std::string 原生支持；对自定义结构体，必须显式提供 operator 或传入比较函数。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

实操建议：

字符串直接用：string s = "abc"; sort(s.begin(), s.end()); do {...} while(next_permutation(s.begin(), s.end()));
自定义类型需满足严格弱序：例如 struct Point { int x,y; };，要定义 bool operator
若不想改结构体，可用 lambda 传入第三个参数：next_permutation(v.begin(), v.end(), [](auto& a, auto& b) { return a.id