-2

The following code uses depth-first search algorithm to generate permutations recursively, I want to know how to change to iteration equivalent without a stack(Pointers can be used). Note that this is very similar to traversing a tree, I try to use the method mentioned in this link, but it is always unsuccessful.

#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);
}
12
  • 1
    the q&a you link already states that this is possible (assuming it is equivalent to traversing a tree). "is it possible?" questions are not so good, because the answer is either just a "yes" or "no". Interpreting it as "please gimme the codez?!" also doesnt make it a good question. When you have issues with code better show that code, no matter how broken. Currently it is unclear why you were not sucessful by applying that answer. Commented Jun 28, 2021 at 13:12
  • You may want to see my answer to the Find all possible combinations of numbers question. It's not the same algorithm as yours, and it's in C, not C++, but I hope it may be helpful.
    – CiaPan
    Commented Jun 28, 2021 at 13:17
  • 1
    Changing a question to make existing, correct answers wrong is generally viewed as bad behavior. Commented Jun 28, 2021 at 13:18
  • 1
    @DrewDormann I am with you, but also consider that already the original question stated " I want to know how to change to iteration equivalent without a stack(Pointers can be used)" Commented Jun 28, 2021 at 13:19
  • 1
    @DrewDormann and now that I think about it the answer does answer that ;) Commented Jun 28, 2021 at 13:20

1 Answer 1

2

You can use std::next_permutation to generate permutations.

#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();
}
3
  • Thank you. Actually I know this way. What I want to know is how to use iteration to rewrite the original algorithm.
    – expression
    Commented Jun 28, 2021 at 13:12
  • 1
    #define N 3 is ugly and should be replaced by const or constexpr. There is guideline for that.
    – Marek R
    Commented Jun 28, 2021 at 13:14
  • 1
    @expression the link has a possible implementation
    – Caleth
    Commented Jun 28, 2021 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.