|
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:
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
Das zweite Verfahren ist vorteilhafter, wenn die Permutationen in einem Array abgelegt sind, da dann das Verschieben von Teilen des Arrays entfällt.
Copyright © 1999 Andreas Borchert, in HTML konvertiert am 29.06.1999 |