Zum Inhalt springen

Algorithmus für Permutationen - Verständnisproblem


Empfohlene Beiträge

Geschrieben (bearbeitet)

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 von smash
Geschrieben

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

Erstelle ein Benutzerkonto oder melde Dich an, um zu kommentieren

Du musst ein Benutzerkonto haben, um einen Kommentar verfassen zu können

Benutzerkonto erstellen

Neues Benutzerkonto für unsere Community erstellen. Es ist einfach!

Neues Benutzerkonto erstellen

Anmelden

Du hast bereits ein Benutzerkonto? Melde Dich hier an.

Jetzt anmelden

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...