Verständnis Permutationsalgorithmus
-
Wie funktioniert denn der Permutationsalgorithmus, der z.b. in std::next_permutation umgesetzt ist?
Wenn ich mir die Definition in <algorithm> anschaue, werden Errinerungen an eine Mathematik-Vorlesung wach.
Allerdings auch wenn ich mir die Ausgaben des Algorithmus auf einer Menge M={1,2,3,4,5} anschaue, komme ich einfach nicht drauf wie der Algorithmus arbeitet.
Deswegen wäre ich sehr froh wenn mir jemand den Algorithmus erklären könnte, da ich bei google meist nur Code zu rekursiv Programmierten Algorithmen finde, ich aber Iterativ arbeiten will.
-
@axels cppreference hat für viele Algorithmen der STL eine mögliche Beispiel Implementierung, so auch für next_permutation
Vielleicht ist das ein guter Ausgangspunkt.
-
@axels sagte in Verständnis Permutationsalgorithmus:
Wie funktioniert denn der Permutationsalgorithmus, der z.b. in std::next_permutation umgesetzt ist?
Wenn ich mir die Definition in <algorithm> anschaue, werden Errinerungen an eine Mathematik-Vorlesung wach.
Allerdings auch wenn ich mir die Ausgaben des Algorithmus auf einer Menge M={1,2,3,4,5} anschaue, komme ich einfach nicht drauf wie der Algorithmus arbeitet.
Deswegen wäre ich sehr froh wenn mir jemand den Algorithmus erklären könnte, da ich bei google meist nur Code zu rekursiv Programmierten Algorithmen finde, ich aber Iterativ arbeiten will.Das hier wird dich vielleicht interessieren:
https://www.jjj.de/fxt/fxtbook.pdf
Ab Seite 102, Permutations and their operations.
-
@wob
Der Code ist schon mal verständlicher als der von <algorithm> aus VS17Aber ich verstehe akutell nicht welche einzelnen Schritte der Algorithmus nacheinander macht, und warum. Ich würde gern den Algorithmus so verstehen das ich ihn prinzipiell auch manuell auf Papier ausführen könnte.
Zugegeben gehört das Thema evtl. eher in das Mathematik-Unterforum.
Den bezug zu C++ habe ich nur hergestellt, da der Implementierte Algorithmus dem aus meiner Vorlesung gleicht, ich aber keinen Namen dazu habe.
-
@axels
Funktion Permutiere mit Laenge und allen ArraysWenn Laenge groesser Anzahl Elemente Return
Zaehler gleich Null
Solange Zaehler kleiner Anzahl Elemente
Ist Position[Zaehler] noch nicht gewaehlt
Permutationsarray[Laenge] sei Element[Zaehler]
und Position[Zaehler] sei gewaehlt
Permutiere mit Laenge +1 ( und den Arrays)
Position[Zaehler] sei nicht gewaehlt
Ende Ist
Inkrementiere Zaehler
Endeschleife
Ende FunktionDas hat dann zur Folge, daß an jeder Position des Permutationsarrays mal jedes Element auftaucht.
Wie das nicht rekursiv geht... grundsätzlich geht alles auch iterativ. Man braucht halt bloß statt
eines rekursiven Aufrufs einen Stack für die Variablen. Bei Austritt aus der Funktion würde es den Stackzeiger dann
dekrementieren, sofern er nicht 0 ist, gefolgt von Goto zu hinter rekursiver Aufruf, und ihn anstelle des rekursiven Aufrufs erhöhen und alles
entsprechend initialisieren, gefolgt von Goto zum Anfang der Funktion. Die iterative Version ist aber noch nicht getestet.