Permutationen II

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]  [Nächstes Kapitel]

Problemstellung: Generierung aller Permutationen von n Objekten, die wir der Einfachheit wegen mit den Zahlen 1 ... n identifizieren. Knuth stellt im Abschnitt 1.2.5 zwei Methoden vor, die jeweils vorgeben, wie aus den vorgegebenen Permutationen für n-1 Objekte die möglichen Permutationen mit n Objekten generiert werden:

Methode 1: Für jede Permutation a1 a2 ... an-1 erzeuge n neue, indem die Zahl n in alle möglichen Plätze eingefügt wird:

     n a1 a2 ... an-1,      a1 n a2 ... an-1      ...,      a1 a2 ... an-1 n     

Methode 2: An jede Permutation a1 a2 ... an-1 wird eine Zahl k für 1 <= k <= n angehängt und jeweils jedes ai um 1 erhöht, falls es >= k ist.

Aus der Permutation 2 3 1 erhalten wir so durch das Anhängen von 1, 2, 3 und 4 die Permutationen

     3 4 2 1,      3 4 1 2,      2 4 1 3,      2 3 1 4     

Das zweite Verfahren ist vorteilhafter, wenn die Permutationen in einem Array abgelegt sind, da dann das Verschieben von Teilen des Arrays entfällt.

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]  [Nächstes Kapitel]
Copyright © 1999 Andreas Borchert, in HTML konvertiert am 29.06.1999