Heap-Algorithmus
# Heap-Algorithmus

Der Heap-Algorithmus generiert alle möglichen Permutationen von $n$ 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 $n-2$ 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 $n$ Objekten ist der Anfang der Folge von Permutationen von $n+1$ Objekten. Es gibt also eine unendliche Folge von Permutationen, die vom Heap-Algorithmus erzeugt werden (Folge A280318 in OEIS).

## Details des Algorithmus

Für eine Menge $C$ aus $n$ 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 $k$ Elementen der Menge – anfänglich $k==n$ und danach $k<n$. Jeder Schritt generiert die $k!$ Permutationen, die mit denselben $n-k$ letzten Elementen enden. Er macht dies, indem er sich selbst einmal mit dem unveränderten $k$ten Element aufruft und dann $k-1$ mal, wobei jeweils das $k$te Element mit den $k-1$ ersten Elementen ausgetauscht wird. Die rekursiven Aufrufe verändern die ersten $k-1$ 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 $k$ der Elemente getroffen werden kann, die in diesem Schritt bearbeitet werden. Wenn $k$ gerade ist, dann wird das letzte Element iterativ mit jedem vorhergehenden Element ausgetauscht. Wenn $k$ ungerade ist, wird das letzte Element immer mit dem ersten ausgetauscht.

Man kann den Algorithmus auch in einem nicht-rekursiven Format schreiben.

## Häufige Fehlimplementierungen

Es ist verlockend, die oben angegebene rekursive Version zu vereinfachen, indem die Anzahl der rekursiven Aufrufe reduziert wird. Zum Beispiel als:

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 $i==k-1$ ist. Die Hälfte davon sind Nulloperationen von $A[i]$ und $A[k-1]$, wenn $k$ gerade ist; und wenn $k$ ungerade ist, führt es zu zusätzlichen Vertauschungen des $k$ten mit dem null-ten Element:

| $n$ | $n!-1$ | swaps | zusätzlich = swaps $-(n!-1)$ |
| - | - | - | - |
| 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 $k-1$ 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 $k-1$ mal durchlaufen wird (wie im 1. vorgestellten Code) oder die Schleife $k$ mal durchlaufen und $i<k-1$ überprüft wird wie in:

Die Wahl der Implementierung ist in erster Linie ästhetischer Natur, aber letztere führt zur doppelt so häufigen Überprüfung des Wertes von $i$.

