Algoritmo de Heap

Um exemplo das 24 permutações e as 23 trocas feitas no algoritmo Heap permutando-se as quatro letras A (âmbar), B (azul), C (ciano) e D (vermelho escuro)

O algoritmo Heap gera todas as permutações possíveis de N objetos. Foi proposto pela primeira vez por B. R. Heap em 1963. O algoritmo minimiza os movimentos para gerar as próximas permutações. O algoritmo gera cada permutação a partir da permutação anterior, trocando um único par de elementos. Os outros elementos N−2 não são alterados. Em uma revisão de 1977 sobre algoritmos de gerar permutações de objetos, Robert Sedgewick concluiu que era o algoritmo o mais eficaz para gerar permutações pelo computador até então.

Detalhes sobre o Algoritmo

Suponha que exista uma permutação contendo N elementos diferentes. B. R. Heap encontrou um método sistemático para escolher, passo-a-passo, um par de elementos para trocar, a fim de produzir todas as permutações possíveis desses elementos exatamente uma vez. O método de Heap pode ser descrito de uma maneira recursiva. Primeiro, define-se um contador i igual a 0. Então, as etapas seguintes são repetidamente executadas até que i seja igual a N. Usamos o algoritmo para gerar o (N − 1)! permutações dos primeiros N − 1 elementos, concatenando o último elemento a cada uma destas permutações. Desta forma, todas as permutações que terminam com o último elemento são geradas. Se N é ímpar, trocamos o primeiro elemento e o último, enquanto que se N é par, pode-se trocar o i-ésimo elemento e o último (não há diferença se N é par ou ímpar na primeira iteração). O contador i é incrementado e a iteração continua. Em cada iteração, o algoritmo produzirá todas as permutações que terminam com o elemento que acabou de ser movido para a "última" posição. O pseudocódigo a seguir produz todas as permutações de um array de dados de comprimento N.

procedure generate(n : integer, A : array of any):
    if n = 1 then
          output(A)
    else
        for i := 0; i < n - 1; 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

Este é o pseudocódigo para a versão não recursiva do algoritmo de Heap.

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

Ver também

• Steinhaus–Johnson–Trotter algorithm