Der Heap-Algorithmus generiert alle möglichen Permutationen von Objekten. Es wurde erstmals 1963 von B.R. Heap vorgeschlagen. Der Algorithmus minimiert die Anzahl der Bewegungen der Elemente: Er generiert jede Permutation aus der vorherigen, indem er ein einzelnes Elementpaar austauscht. Die anderen Elemente werden nicht verändert. Bei einer Überprüfung von Algorithmen zur Erzeugung von Permutationen im Jahr 1977 kam Robert Sedgewick zu dem Schluss, dass dies zu dieser Zeit der effektivste Algorithmus zur Erzeugung von Permutationen per Computer war.
Die durch den Heap-Algorithmus erzeugte Folge von Permutationen von Objekten ist der Anfang der Folge von Permutationen von Objekten. Es gibt also eine unendliche Folge von Permutationen, die vom Heap-Algorithmus erzeugt werden (Folge A280318 in OEIS).
Details des Algorithmus Bearbeiten
Für eine Menge aus verschiedenen Elementen fand Heap eine systematische Methode, bei jedem Schritt ein Elementpaar zum Vertauschen auszuwählen, um dabei jede mögliche Permutation dieser Elemente genau einmal zu erzeugen.
Der Heap-Algorithmus wird rekursiv als Teile-und-herrsche-Verfahren beschrieben und arbeitet bei jedem Schritt auf den ersten Elementen der Menge – anfänglich und danach . Jeder Schritt generiert die Permutationen, die mit denselben letzten Elementen enden. Er macht dies, indem er sich selbst einmal mit dem unveränderten ten Element aufruft und dann mal, wobei jeweils das te Element mit den ersten Elementen ausgetauscht wird. Die rekursiven Aufrufe verändern die ersten Elemente. Es wird eine Regel benötigt, die bei jeder Iteration auswählt, welches Element mit dem letzten ausgetauscht werden soll. Die Methode von Heap besagt, dass diese Auswahl durch die Parität der Anzahl der Elemente getroffen werden kann, die in diesem Schritt bearbeitet werden. Wenn gerade ist, dann wird das letzte Element iterativ mit jedem vorhergehenden Element ausgetauscht. Wenn ungerade ist, wird das letzte Element immer mit dem ersten ausgetauscht.
// der anfängliche Aufruf von generate geschieht mit k == length(A) procedure generate(k : integer, A : array of any): if k = 1 then output(A) else // erzeuge Permutationen mit unverändertem kten Element generate(k - 1, A) // erzeuge Permutationen mit dem kten Element vertauscht mit jedem (k-1)sten Element // alle Array-Zugriffe sind 0-basiert, d.h. das kte Element ist bei [k-1] for i := 0; i < k-1; i += 1 do // vertausche 2 Elemente in Abhängigkeit von der Parität von k (gerade oder ungerade) if k is even then swap(A[i], A[k-1]) else swap(A[0], A[k-1]) end if generate(k - 1, A) end for end if Man kann den Algorithmus auch in einem nicht-rekursiven Format schreiben.
procedure generate(n : integer, A : array of any): // c ist eine Codierung des Stapelzustands. c[k] codiert den Schleifen-Zähler, wenn generate(k - 1, A) aufgerufen wird c : array of int for i := 0; i < n; i += 1 do c[i] := 0 end for output(A) // i verhält sich ähnlich wie der Stapelzeiger i := 1; while i < n do if c[i] < i then if i is even then swap(A[0], A[i]) else swap(A[c[i]], A[i]) end if output(A) // Vertauschung ist durchgeführt worden und hat die Schleife beendet. Simuliert das Inkrement des Schleifen-Zählers c[i] += 1 // Simuliert einen rekursiven Aufruf, der den Basisfall erreicht, indem der Zeiger auf den Basisfall analog im Array durchgeführt wird i := 1 else // das Aufrufen von generate(i+1, A) endet, wenn die Schleife endet. // Setzt den Status zurück und simuliert das Stapeln durch Inkrementieren des Zeigers. c[i] := 0 i += 1 end if end while Häufige Fehlimplementierungen Bearbeiten
Es ist verlockend, die oben angegebene rekursive Version zu vereinfachen, indem die Anzahl der rekursiven Aufrufe reduziert wird. Zum Beispiel als:
procedure generate(k : integer, A : array of any): if k = 1 then output(A) else // rekursiver Aufruf einmal für jedes k for i := 0; i < k; i += 1 do generate(k - 1, A) // Vertauschung abhängig von der Parität von k (gerade oder ungerade) if k is even then // Nulloperation, wenn i == k-1 swap(A[i], A[k-1]) else // überflüssige, zusätzliche Vertauschung wenn i == k-1 swap(A[0], A[k-1]) end if end for end if Diese Implementierung wird erfolgreich alle Permutationen erzeugen, minimiert jedoch nicht die Anzahl der Vertauschungen. Wenn sich die rekursiven Aufrufstapel zurück abwickeln, führt dies zu zusätzlichen Vertauschungen auf jeder Ebene, wenn ist. Die Hälfte davon sind Nulloperationen von und , wenn gerade ist; und wenn ungerade ist, führt es zu zusätzlichen Vertauschungen des ten mit dem null-ten Element:
| swaps | zusätzlich = swaps | ||
|---|---|---|---|
| 1 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 |
| 3 | 5 | 6 | 1 |
| 4 | 23 | 27 | 4 |
| 5 | 119 | 140 | 21 |
| 6 | 719 | 845 | 126 |
| 7 | 5039 | 5922 | 883 |
| 8 | 40319 | 47383 | 7064 |
| 9 | 362879 | 426456 | 63577 |
Diese zusätzlichen Vertauschungen verändern die Reihenfolge der Vor-Elemente beträchtlich.
Die zusätzlichen Vertauschungen können vermieden werden, indem entweder ein zusätzlicher rekursiver Aufruf vor der Schleife hinzugefügt und die Schleife mal durchlaufen wird (wie im 1. vorgestellten Code) oder die Schleife mal durchlaufen und überprüft wird wie in:
procedure generate(k : integer, A : array of any): if k = 1 then output(A) else // rekursiver Aufruf einmal für jedes k for i := 0; i < k; i += 1 do generate(k - 1, A) // vermeide Vertauschung, wenn i==k-1 if (i < k - 1) // Vertauschung abhängig von der Parität von k if k is even then swap(A[i], A[k-1]) else swap(A[0], A[k-1]) end if end if end for end if Die Wahl der Implementierung ist in erster Linie ästhetischer Natur, aber letztere führt zur doppelt so häufigen Überprüfung des Wertes von .
Siehe auch Bearbeiten
Einzelnachweise Bearbeiten
- B. R. Heap: Permutations by Interchanges. In: The Computer Journal. 6. Jahrgang, Nr. 3, 1963, S. 293–4, doi:10.1093/comjnl/6.3.293 (oxfordjournals.org [PDF]).
- R. Sedgewick: Permutation Generation Methods. In: ACM Computing Surveys. 9. Jahrgang, Nr. 2, 1977, S. 137–164, doi:10.1145/356689.356692.
- Robert Sedgewick: a talk on Permutation Generation Algorithms.