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

c++ 全排列

news 2025/7/22 18:25:30

在C++中，全排列（permutation）可以使用递归算法或标准库函数来实现。以下是使用递归和STL库std::next_permutation来生成一个集合的全排列的两种方法。

方法一：递归算法

递归方法通过交换元素来生成所有可能的排列组合。

#include <iostream>
#include <vector>
#include <algorithm>void permute(std::vector<int>& nums, int l, int r, std::vector<std::vector<int>>& result) {if (l == r) {result.push_back(nums);} else {for (int i = l; i <= r; ++i) {std::swap(nums[l], nums[i]);permute(nums, l + 1, r, result);std::swap(nums[l], nums[i]); // backtrack}}
}int main() {std::vector<int> nums = {1, 2, 3};std::vector<std::vector<int>> result;permute(nums, 0, nums.size() - 1, result);for (const auto& perm : result) {for (int num : perm) {std::cout << num << " ";}std::cout << std::endl;}return 0;
}

方法二：使用STL库`std::next_permutation`

std::next_permutation是C++标准库中提供的函数，用于生成字典序中的下一个排列。可以通过不断调用该函数来生成所有的排列组合。

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> nums = {1, 2, 3};std::sort(nums.begin(), nums.end()); // 确保初始状态是最小排列do {for (int num : nums) {std::cout << num << " ";}std::cout << std::endl;} while (std::next_permutation(nums.begin(), nums.end()));return 0;
}

方法三：使用C++11或更高版本的`std::vector`和`std::algorithm`

如果您使用的是C++11或更高版本，可以结合std::vector和std::algorithm来简化代码。

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> nums = {1, 2, 3};do {for (const int& num : nums) {std::cout << num << " ";}std::cout << std::endl;} while (std::next_permutation(nums.begin(), nums.end()));return 0;
}