c++ 全排列

在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;
}

这三种方法都能有效地生成并打印一个集合的所有排列。第一种方法通过递归和回溯的方式，适合理解递归思想和回溯算法的实现；第二种和第三种方法利用标准库函数std::next_permutation，简化了代码实现，适合实际项目中的快速应用。