Heap-Algorithmus

aus Wikipedia, der freien Enzyklopädie
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 erzeugt durch den Heap-Algorithmus, bei dem jede Permutation farbcodiert ist (1 = blau, 2 = grün, 3 = gelb, 4 = rot)

Der Heap-Algorithmus generiert alle möglichen Permutationen von Objekten. Es wurde erstmals 1963 von B.R. Heap vorgeschlagen.[1] 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.[2]

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

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.[3]

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

Steinhaus-Johnson-Trotter-Algorithmus

Einzelnachweise

  1. B. R. Heap: Permutations by Interchanges. In: The Computer Journal. 6, Nr. 3, 1963, S. 293–4. doi:10.1093/comjnl/6.3.293.
  2. R. Sedgewick: Permutation Generation Methods. In: ACM Computing Surveys. 9, Nr. 2, 1977, S. 137–164. doi:10.1145/356689.356692.
  3. Robert Sedgewick: a talk on Permutation Generation Algorithms.