The question is rather a sporting interest, rather than something very much needed

In general, there is a rather banal algorithm for generating various permutations of a string with factorial complexity.

void permutations(std::string s, int pos = 0) { if (pos >= s.size()) { std::cout << s << '\n'; return; } else { for (int i = pos; i < s.size(); ++i) { std::swap(s[i], s[pos]); permutations(s, pos + 1); std::swap(s[i], s[pos]); } } }

It is known from theory that any recursion can be rewritten iteratively using stack emulation.

update how to do this in this case without using any data structures to emulate a call stack?

  • 3
    If you prohibit the emulation of recursion manually, using an explicit stack (queue, etc.), then you will have to abandon the "theory", according to which "any recursion can be rewritten iteratively." In the general case, the rewriting of recursion iteratively is possible just and only through the transition to an explicit stack. This is what "theory" means. In this case, the problem can be solved without recursion, but not in the general case. - AnT
  • @AnT ok, I refuse - ampawd
  • one
    It seems to me that the more interesting question would be not “without using structures to emulate a stack” (in the end, who said that I use a queue to emulate a stack, and not just like that?), But “O (1) from memory” . - VladD
  • There are several solutions to the problem. The most famous can be found, for example, here . Without asking a question on SO, it was possible to find a solution through Google in less than a minute and a half. - Zealint
  • @Zealint I can use Google, I don’t need it here, the whole point is that here someone will provide his unique solution - ampawd

2 answers 2

The stupidest and most versatile option is emulating a recursion using a stack:

 void permutations(const string& s) { struct item { string s; int pos; }; stack<item>task; task.push(item{s,0}); while(!task.empty()) { item i = task.top(); task.pop(); if (i.pos >= issize()) { std::cout << is << '\n'; continue; } else { for (int j = i.pos; j < issize(); ++j) { std::swap(is[j], is[i.pos]); task.push(item{is,i.pos+1}); std::swap(is[j], is[i.pos]); } } } }
  • well, I forgot to note that the stack cannot be emulated)) - ampawd
  • one
    Then we climb into 4A Knut and use any of the permutation generation algorithms listed there. Because, as I recall, only terminal recursion is eliminated directly without a stack (even compilers do this). In this case, it is not her, so the algorithm must be more or less altered. Imho :) - Harry
  • @ampawd: Well, you yourself said: "It is known from theory that any recursion can be rewritten iteratively." This theory means that there is always the possibility of a "stack emulation". Without "stack emulation," in general, it is impossible to "rewrite iteratively iteratively." In this case, you're lucky: an iterative algorithm exists — Narayana’s well-known algorithm ( ru.wikipedia.org/wiki/… ). But in general - no. - AnT

You can use the non-recursive Narayana Algorithm , its complexity is O (n).

Algorithm:

Step 1: find the largest j for which a [j] <a [j + 1].

Step 2: increase a [j]. To do this, find the largest l, for which a [l]> a [j]. Then swap a [j] and a [l].

Step 3: write the sequence a [j + 1], ..., a [n] in the reverse order.