c++运用递归实现全排列

在C++中，递归是一种常见的算法，可以用于生成所有可能的排列组合，如全排列。全排列是指从给定的一组元素中取出所有可能的不同元素序列。这里是一个简单的例子，展示了如何使用递归实现全排列：

#include <iostream>
#include <vector>

// 交换两个元素
void swap(std::vector<int>& arr, int i, int j) {
    std::swap(arr[i], arr[j]);
}

// 递归函数计算全排列
std::vector<std::vector<int>> permute(std::vector<int>& arr, int start = 0) {
    // 如果到达数组的最后一个元素，直接返回包含当前元素的一个子集
    if (start == arr.size() - 1) {
        return {arr};
    }

    // 否则，对剩余的元素递归地应用全排列，并将结果存储在一个 vector 中
    std::vector<std::vector<int>> result;
    for (int i = start; i < arr.size(); ++i) {
        // 将当前元素移到起始位置
        swap(arr, start, i);
        
        // 对剩余元素继续求全排列
        result.push_back(permute(arr, start + 1));
        
        // 撤销操作，恢复原状
        swap(arr, start, i); // 这一步很重要，否则会产生重复排列
    }
    
    return result;
}

int main() {
    std::vector<int> input = {1, 2, 3};
    std::vector<std::vector<int>> permutations = permute(input);
    for (const auto& permutation : permutations) {
        for (int num : permutation) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    }
    return 0;
}

在这个代码中，`permute`函数是递归的核心，它会为每个未处理的元素生成一个新的排列。每次递归调用都会产生一个新的排列，直到处理完所有元素。