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.


  • Gesperrt

    @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 VS17

    Aber 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 Arrays

    Wenn 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 Funktion

    Das 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.


Anmelden zum Antworten