-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);
}
Drew Dormann
  • 59,987
  • 13
  • 123
  • 180
expression
  • 177
  • 4
  • 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. – 463035818_is_not_an_ai Jun 28 '21 at 13:12
  • You may want to see [my answer](https://stackoverflow.com/a/67038660/733637) to the _[Find all possible combinations of numbers](https://stackoverflow.com/questions/67035007/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 Jun 28 '21 at 13:17
  • "Can I rewrite this stack-based algorithm without a stack?... but I want it to be exactly the same algorithm" is a very annoying question. The Pandita algorithm is similar, but it uses the sequence itself as the stack: https://stackoverflow.com/questions/40752319/algorithm-to-list-unique-permutations-of-string-with-duplicate-letters/40756214#40756214 – Matt Timmermans Jun 28 '21 at 13:18
  • 1
    Changing a question to make existing, correct answers wrong is generally viewed as [_bad behavior_](https://meta.stackoverflow.com/questions/290297/how-much-change-to-the-question-is-too-much). – Drew Dormann Jun 28 '21 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)" – 463035818_is_not_an_ai Jun 28 '21 at 13:19
  • 1
    @DrewDormann and now that I think about it the answer does answer that ;) – 463035818_is_not_an_ai Jun 28 '21 at 13:20
  • @463035818_is_not_a_number then I'm with you. – Drew Dormann Jun 28 '21 at 13:20
  • please don't tag C and C++ unless the question is about interoperation between the two (different) languages. And when you realize that the question was not exactly asking what you wanted to ask for it is better to open a new question rather than to invalidate existing answers – 463035818_is_not_an_ai Jun 28 '21 at 13:21
  • @expression given your rejection of an answer that uses ``, is this possibly a homework assignment? The answer that's here now both _"use[s] iteration"_ and _"rewrite[s] the original algorithm"_ – Drew Dormann Jun 28 '21 at 13:26
  • Sorry, I didn’t think about it clearly at the beginning. I should add another question, but someone has already answered it. Now I can’t delete the question. – expression Jun 28 '21 at 13:30
  • @expression I have rolled back this question to what it was when an answer was given. You are very welcome to ask a new question. Do be careful when choosing between [c] and [c++] tags. They are not the same. – Drew Dormann Jun 28 '21 at 13:33
  • Usually DFS requires a stack-like structure. You could use `std::stack` for that, but that's not much different from recursion. See [here](https://www.geeksforgeeks.org/iterative-depth-first-traversal/) for an example. – rustyx Jun 28 '21 at 13:38

1 Answers1

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();
}
MikeCAT
  • 73,922
  • 11
  • 45
  • 70
  • Thank you. Actually I know this way. What I want to know is how to use iteration to rewrite the original algorithm. – expression Jun 28 '21 at 13:12
  • 1
    `#define N 3` is ugly and should be replaced by `const` or `constexpr`. There is [guideline for that](https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Res-macros2). – Marek R Jun 28 '21 at 13:14
  • 1
    @expression the link has a [possible implementation](https://en.cppreference.com/w/cpp/algorithm/next_permutation#Possible_implementation) – Caleth Jun 28 '21 at 13:26