Permutationen iterativ erzeugen

[Brigitta]

Hallo,

ich versuche, einen iterativen (nicht rekursiven) Algorithmus zu finden,
der mir alle Permutationen eines Strings erzeugt. Also mit
z.B. myString = "abcd" soll mir der Algorithmus alle 4! = 24 Permutationen erzeugen.
Mir geht es nicht um eine fertige Lösung in Java, Python oder einer anderen Programmiersprache, dazu findet sich vieles im Netz.
Was ich suche ist:
Ein iterativer Algorithmus in Pseudocode, damit ich überhaupt verstehen kann, wie er funktioniert. Also quasi die Erklärung des Permutations-Algorithmus.
Ich habe jetzt mehrere Tage vergeblich gesucht und immer nur fertige Lösungen gefunden.
Hätte jemand einen Link für mich, wo ein solcher Algorithmus in Pseudocode erklärt wird?
Rekursiv habe ich das Problem gelöst. Aber mein Ehrgeiz ist, das auch iterativ hinzukriegen.

Vielen Dank für Eure Hilfe
Grüße
Brigitta

[Thomas Koenig]

Post by Brigitta
Ein iterativer Algorithmus in Pseudocode, damit ich überhaupt
verstehen kann, wie er funktioniert. Also quasi die Erklärung
des Permutations-Algorithmus.

Wie sieht es mit

https://en.wikipedia.org/wiki/Heap%27s_algorithm

und

https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm

aus?

[Stefan Ram]

Post by Brigitta
Also quasi die Erklärung des Permutations-Algorithmus.

TAOCP, Band 4, Abschnitt "Generating All Permutations".

[Burkart Venzke]

Hallo Brigitta,

wenn du von dem aufsteigend sortierten String "abcd" ausgehst, erhälst
du den nächsten, wenn du die letzten beiden Zeichen vertauscht - sofern
diese nicht schon umgekehrt sortiert sind. Falls doch, Zeichen davor auf
nächst größeres Zeichen setzen und Rest aufsteigend sortieren.

abcd
-> abdc letzte beiden Zeichen vertauschen
-> acbd c nächst größere Zeichen (zu b), bd normal sortiert
-> acdb letzte beiden Zeichen vertauschen
-> adbc d nächst größere Zeichen (zu c), bc normal sortiert
usw.

Hilft dir das weiter?

Gruß, Gurkart