thumb|90px|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 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ã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 Suponha que exista uma permutação contendo 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, 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, 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
Categoria:Algoritmos Categoria:Permutação