使用c++语言编写计算全排列的算法 不使用递归

以下是使用c语言编写的计算全排列的算法，不使用递归：

#include <stdio.h>

// 交换两个元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 计算全排列
void permute(int arr[], int n) {
    int i, j;

    // 初始时所有元素都是未标记的
    int marked[n];
    for (i = 0; i < n; i++) {
        marked[i] = 0;
    }

    // 模拟栈的操作，用来存储每一步的状态
    int stack[n];
    int top = -1;

    // 将第一个元素入栈
    stack[++top] = 0;
    marked[0] = 1;

    while (top >= 0) {
        // 取出栈顶元素
        i = stack[top];

        // 如果栈顶元素是最后一个元素，说明已经找到了一个排列
        if (i == n-1) {
            for (j = 0; j < n; j++) {
                printf("%d ", arr[j]);
            }
            printf("\n");
            top--;
            marked[i] = 0;
            continue;
        }

        // 将下一个未标记的元素入栈
        for (j = 0; j < n; j++) {
            if (!marked[j]) {
                stack[++top] = j;
                marked[j] = 1;
                swap(&arr[i+1], &arr[j]);
                break;
            }
        }

        // 如果没有未标记的元素，说明这个状态已经处理完成，可以回溯
        if (j == n) {
            top--;
            marked[i] = 0;
            swap(&arr[i], &arr[i+1]);
        }
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    permute(arr, n);
    return 0;
}

该算法使用了一个栈来模拟递归的操作，同时使用一个数组来记录每个元素是否已经被标记过。算法的时间复杂度为 $O(n!)$，空间复杂度为 $O(n)$。