C++编程实现错排问题的递归算法和迭代算法

在C++中，错排问题通常是指对数组进行全排列的问题。这里我将分别介绍递归算法和迭代算法的实现。

**递归算法** (也称回溯法)：

#include <iostream>
using namespace std;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void permuteRecursion(int arr[], int start, int end) {
    if (start == end)
        cout << arr << endl;
    else {
        for (int i = start; i <= end; i++) {
            swap(&arr[start], &arr[i]);
            permuteRecursion(arr, start + 1, end);
            // 撤销当前交换，回到上一步状态
            swap(&arr[start], &arr[i]);
        }
    }
}

void generatePermutations(int n) {
    int* arr = new int[n];
    for (int i = 0; i < n; i++)
        arr[i] = i + 1;
    permuteRecursion(arr, 0, n - 1);
    delete[] arr;
}

int main() {
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;
    generatePermutations(n);
    return 0;
}

**迭代算法** (也称为栈回溯法)：

#include <iostream>
#include <vector>
using namespace std;

void generatePermutations(vector<int>& nums, vector<vector<int>>& results, int index) {
    if (index == nums.size()) {
        results.push_back(nums);
        return;
    }

    for (int i = 0; i < nums.size(); ++i) {
        // 交换当前元素的位置
        swap(nums[index], nums[i]);

        // 继续处理剩余元素
        generatePermutations(nums, results, index + 1);

        // 回溯，恢复到原始位置
        swap(nums[index], nums[i]); // 这里也可以选择不恢复，取决于需求
    }
}

vector<vector<int>> permuteIterative(int n) {
    vector<int> nums(n), res;
    for (int i = 0; i < n; i++)
        nums[i] = i + 1;

    vector<vector<int>> results;
    generatePermutations(nums, results, 0);

    return results;
}

int main() {
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;
    auto permutations = permuteIterative(n);
    for (const auto& p : permutations)
        cout << p << endl;

    return 0;
}

在这两个示例中，递归算法通过不断交换并尝试所有可能性直到达到结束条件（只有一个元素），而迭代算法则是通过维护一个结果列表并在每次循环结束后回溯来避免重复。