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.

Ein Schema der 24 Permutationen und der 23 Vertauschungen, die im Heap-Algorithmus verwendet werden, wobei die vier Buchstaben A (braun), B (blau), C (cyan) und D (rot) permutieren

Polardiagramm aller Permutationen von $n=4$ erzeugt durch den Heap-Algorithmus, bei dem jede Permutation farbcodiert ist (1 = blau, 2 = grün, 3 = gelb, 4 = rot)

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.

// 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

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 $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:

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 $i$.

Siehe auch

Steinhaus-Johnson-Trotter-Algorithmus