Algoritmo de Heap

Un mapa de las 24 permutaciones y los 23 intercambios utilizados en Algoritmo de Heap permuting las cuatro letras A (ámbar), B (azul), C (ciánico) y D (rojo oscuro)

El Algoritmo de Heap genera todas las permutaciones posibles de N objetos. Fue propuesto por primera vez por B. R. Heap En 1963.​ El algoritmo minimiza movimiento: genera cada permutación de la anterior intercambiando un par de elementos; los otros N−2 elementos no se alteran. En una revisión de 1977 de algoritmos generadores de permutación, Robert Sedgewick concluyó que sea en aquel tiempo el algoritmo más eficaz para generar permutaciones por computadora.​

Detalles del algoritmo

Supongamos que tenemos una permutación que contiene N elementos diferentes. Heap encontró un método sistemático para escoger en cada paso un par de elementos para cambiar, para producir cada permutación posible de estos elementos exactamente una vez. Describamos el método de Heap de una manera recursiva. Primero pusimos un contador i a 0. Realizamos los siguientes pasos repetidamente hasta que i es igual a N. Utilizamos el algoritmo para generar el (N − 1)! permutaciones de los primeros N − 1 elementos, contiguos el último elemento a cada cual de estos. Esto genera todas las permutaciones que terminan con el último elemento. Entonces si N es impar, cambiamos el primero elemento y el último, mientras que si N es par podemos cambiar el i-ésimo elemento y el último (no hay ninguna diferencia entre N par e impar en la primera iteración). Añadimos uno al contador i y repetimos. En cada iteración, el algoritmo producirá todas las permutaciones que terminan con el elemento que acaba de ser movido a la "última" posición. El siguiente pseudocode genera todas las permutaciones de una matriz de datos de longitud N.

procedure generate(n : integer, A : array of any):
    if n = 1 then
          output(A)
    else
        for i := 0; i < n; i += 1 do
            generate(n - 1, A)
            if n is even then
                swap(A[i], A[n-1])
            else
                swap(A[0], A[n-1])
            end if
        end for
    end if

También se puede escribir el algoritmo en un formato no recursivo.​

procedure generate(n : integer, A : array of any):
    c : array of int

    for i := 0; i < n; i += 1 do
        c[i] := 0
    end for

    output(A)
    
    i := 0;
    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)
            c[i] += 1
            i := 0
        else
            c[i] := 0
            i += 1
        end if
    end while

Ve también

• Steinhaus–Johnson–Trotter algorithm

Referencias

• Datos: Q16907296