如何用递归实现这个功能?
时间: 2024-09-25 14:17:16 浏览: 13
递归是一种有效的方法来生成一个序列的全排列。下面是一个简单的C++递归函数实现的例子:
```cpp
#include <iostream>
#include <vector>
void permute(int start, std::vector<int>& arr, std::string& current) {
if (start == arr.size()) { // 当前序列已完整,打印结果
for (int i : arr) {
std::cout << std::setw(5) << i; // 保持5个字符宽度
}
std::cout << '\n';
} else {
for (int i = start; i < arr.size(); ++i) { // 交换开始位置后的元素
std::swap(arr[start], arr[i]);
permute(start + 1, arr, current + std::to_string(arr[start])); // 递归调用,更新当前序列
std::swap(arr[start], arr[i]); // 回溯,恢复原始顺序
}
}
}
int main() {
int n;
std::cin >> n;
std::vector<int> arr(1, 1); // 初始化数组,从1开始
std::string result;
permute(0, arr, result);
return 0;
}
```
在这个例子中,`permute`函数接受起始位置、当前排列的数组和一个字符串变量来记录当前状态。在每次递归调用中,它会选择一个未使用的数字放到当前的位置,然后对剩下的数字再次进行排列。最后,当起始位置等于数组大小时,就得到了一个完整的排列,打印出来。