是否可以将此递归更改为没有堆栈的迭代？

Question

以下代码使用深度优先搜索算法递归生成排列，我想知道如何在没有堆栈的情况下更改为迭代等效（可以使用指针）。注意这和遍历树很像，我尝试使用this link中提到的方法，但总是不成功

#include <stdio.h>

#define N 3
int A[N];

void dfs(int n, int mask) {
    if (n == N) {
        for (int j = 0; j < N; ++j) {
            printf("%d ", A[j]);
        }
        puts("");
    } else
        for (int i = 0; i < N; i++)
            if ((mask & (1 << i)) == 0) {
                A[n] = i + 1;
                dfs(n + 1, mask | (1 << i));
            }
}

int main() {
    dfs(0, 0);
}

Answer 1

您可以使用 std::next_permutation 生成排列。

#include <stdio.h>
#include <algorithm>

#define N 3
int A[N];

void perm() {
    for (int i = 0; i < N; i++) {
        A[i] = i + 1;
    }
    do {
        for (int j = 0; j < N; ++j) {
            printf("%d ", A[j]);
        }
        puts("");
    } while (std::next_permutation(A, A + N));
}

int main() {
    perm();
}