Hallo,

ich suche nach einem Algorithmus, der es mit ermöglicht, Permutationen aus einer Menge von Elementen zu bilden. Am besten wäre es, wenn die Permutationen in lexikographischer Reihenfolge ausgegeben werden würden und wenn ich jede Permutation einzeln errechnen kann, ohne alle anderen Permutationen zu kennen.

Auf meine Suche bin ich auf folgende Seite gestoßen:

Ein Algorithmus zur Ermittlung der lexikographisch nächsten Permutation zu einem vorgegebenen Inputvektor

Ich glaube, dass ist schon fast das was ich will, aber ich vertsehe es leider nicht richtig. Die Srache S-Plus kann ich leider auch nicht.

Versteht jemand wie der Algorithmus genau abläuft und kann ihn mir besser erklären?

Oder möchte jemand einen anderen Algorithmus vorschlagen?

Vielen Dank im Voraus.

Bearbeitet 15. Oktober 200915 j von smash

Ich glaube, dass ist schon fast das was ich will, aber ich vertsehe es leider nicht richtig. Die Srache S-Plus kann ich leider auch nicht.

Du musst ja nicht die Sprache können, sondern sie nur lesen, aber es ist Doch eigentlich recht einfach. Ich nehme mal das Beispiel daraus:

1 2 7 6 5 3 4

Versucht darin das Pivot Element zu finden, das macht er indem er die Differenzen der stellen bildet (unter 3):

1-2 = -1

2-7 = -5

7-6 = 1

6-5 = 1

3-4 = -1

Die Idee besteht nun darin, dass das erste Element kleiner dem zweiten, usw ist. für diesen Fall heißt das, dass das erste und zweite Element schon lexikographisch "korrekt" sortiert wurden.

Er zerlegt jetzt die Element so, dass er zwei Teile bekommt: 1 2 7 und 3 4 das wären seine "fallenden Folgen", denn die Differenzen sind klein. Das Pivotelemt ist das Element, von dem dann rechts ab sortiert wird und in diesem Fall wäre das in diesem Fall die 5, denn danach beginnt eine "fallende Folge" (das wäre hier bis 6).