当前位置：首页 > article >正文

C++中实现全排列方法

article 2025/3/4 22:51:40

在 C++ 中实现全排列（Permutations）有多种方法，这里我将介绍两种常用的方法：递归方法和使用 STL 的 next_permutation 方法。

方法 1：递归方法

递归方法通过固定一个元素的位置，然后对剩余的元素进行全排列来实现。

#include <iostream>
#include <vector>

using namespace std;

void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
if (start == nums.size()) {
result.push_back(nums);
return;
}
for (int i = start; i < nums.size(); ++i) {
swap(nums[start], nums[i]); // 固定一个位置
permute(nums, start + 1, result); // 递归调用
swap(nums[start], nums[i]); // 回溯，恢复原数组
}
}

vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
permute(nums, 0, result);
return result;
}

int main() {
vector<int> nums = {1, 2, 3};
vector<vector<int>> result = permute(nums);
for (const auto& perm : result) {
for (int num : perm) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
方法 2：使用 STL 的 next_permutation 方法

这种方法利用 C++ STL 中的 next_permutation 函数，它可以生成下一个排列直到所有的排列都被生成。

#include <iostream>
#include <vector>
#include <algorithm> // for std::next_permutation

using namespace std;

vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end()); // 先排序，确保从最小的排列开始
do {
result.push_back(nums); // 将当前的排列加入结果集
} while (next_permutation(nums.begin(), nums.end())); // 生成下一个排列，直到所有排列都被生成
return result;
}

int main() {
vector<int> nums = {1, 2, 3};
vector<vector<int>> result = permute(nums);
for (const auto& perm : result) {
for (int num : perm) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
说明：