Algoritmo de Heap
O algoritmo Heap gera todas as permutações possíveis de N objetos. Foi proposto pela primeira vez por B. R. Heap em 1963. [1] 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. [2]
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 ifEste é o pseudocódigo para a versão não recursiva do algoritmo de Heap.[3]
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 whileVer também
- Steinhaus–Johnson–Trotter algorithm
