递归全排列vector
时间: 2023-11-14 22:07:31 浏览: 21
以下是递归全排列vector的代码实现:
```c++
void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
if (start == nums.size() - 1) {
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;
}
```
相关问题
递归全排列
递归全排列可以通过交换元素实现。具体步骤如下:
1. 设有n个元素,将第1个元素依次与第2至n个元素交换,得到n种不同的排列;
2. 对于每一种排列,将第2个元素依次与第3至n个元素交换,得到(n-1)种不同的排列;
3. 以此类推,对于每种排列,将第i个元素依次与第(i+1)至n个元素交换,得到(n-i+1)种不同的排列;
4. 直到第n个元素与第n个元素交换完成,输出排列结果。
这个过程可以通过递归实现,具体代码如下:
```
void permute(vector<int> &nums, int begin, vector<vector<int>> &result) {
if (begin == nums.size() - 1) {
result.push_back(nums);
return;
}
for (int i = begin; i < nums.size(); i++) {
swap(nums[begin], nums[i]);
permute(nums, begin + 1, result);
swap(nums[begin], nums[i]);
}
}
```
其中,`nums`为待排列的元素,`begin`为当前排列的起始位置,`result`用于存储所有的排列结果。在每次交换元素之后,递归调用`permute`函数,直到排列完成,将排列结果存入`result`中。
来一段C++使用递归实现全排列
好的,以下是使用递归实现全排列的 C++ 代码示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void permute(vector<int>& nums, int start, vector<vector<int>>& res) {
if (start == nums.size()) { // 当 start 等于数组长度时,说明已经排列完成
res.push_back(nums);
return;
}
for (int i = start; i < nums.size(); ++i) { // 依次将 nums[start] 和 nums[i] 交换,然后递归处理子问题
swap(nums[start], nums[i]);
permute(nums, start + 1, res);
swap(nums[start], nums[i]); // 恢复 nums[start] 和 nums[i] 的原始值,以便进行下一次交换
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
permute(nums, 0, res);
return res;
}
int main() {
vector<int> nums = {1, 2, 3};
vector<vector<int>> res = permute(nums);
for (auto& vec : res) {
for (int num : vec) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
```
该算法的时间复杂度为 O(n!),因为一共有 n! 种排列方式。