b'\n_START_ARTICLE_\nAlgoritmo de Heap\n_START_PARAGRAPH_\nO algoritmo Heap gera todas as permuta\xc3\xa7\xc3\xb5es poss\xc3\xadveis de N objetos. Foi proposto pela primeira vez por B. R. Heap em 1963.  O algoritmo minimiza os movimentos para gerar as pr\xc3\xb3ximas permuta\xc3\xa7\xc3\xb5es. O algoritmo gera cada permuta\xc3\xa7\xc3\xa3o a partir da permuta\xc3\xa7\xc3\xa3o anterior, trocando um \xc3\xbanico par de elementos. Os outros elementos N\xe2\x88\x922 n\xc3\xa3o s\xc3\xa3o alterados. Em uma revis\xc3\xa3o de 1977 sobre  algoritmos de gerar permuta\xc3\xa7\xc3\xb5es de objetos, Robert Sedgewick concluiu que era o algoritmo o mais eficaz para gerar permuta\xc3\xa7\xc3\xb5es pelo computador at\xc3\xa9 ent\xc3\xa3o.\n_START_SECTION_\nDetalhes sobre o Algoritmo\n_START_PARAGRAPH_\nSuponha que exista uma permuta\xc3\xa7\xc3\xa3o contendo N elementos diferentes. B. R. Heap encontrou um m\xc3\xa9todo sistem\xc3\xa1tico para escolher, passo-a-passo, um par de elementos para trocar, a fim de produzir todas as permuta\xc3\xa7\xc3\xb5es poss\xc3\xadveis desses elementos exatamente uma vez. O m\xc3\xa9todo de Heap pode ser descrito de uma maneira recursiva. Primeiro, define-se um contador i igual a 0. Ent\xc3\xa3o, as etapas seguintes s\xc3\xa3o repetidamente executadas at\xc3\xa9 que i seja igual a N. Usamos o algoritmo para gerar o (N\xc2\xa0\xe2\x88\x92\xc2\xa01)! permuta\xc3\xa7\xc3\xb5es dos primeiros N\xc2\xa0\xe2\x88\x92\xc2\xa01 elementos, concatenando o \xc3\xbaltimo elemento a cada uma destas permuta\xc3\xa7\xc3\xb5es. Desta forma, todas as permuta\xc3\xa7\xc3\xb5es que terminam com o \xc3\xbaltimo elemento s\xc3\xa3o geradas. Se N \xc3\xa9 \xc3\xadmpar, trocamos o primeiro elemento e o \xc3\xbaltimo, enquanto que se N \xc3\xa9 par, pode-se trocar o i-\xc3\xa9simo elemento e o \xc3\xbaltimo (n\xc3\xa3o h\xc3\xa1 diferen\xc3\xa7a se N \xc3\xa9 par ou \xc3\xadmpar na primeira itera\xc3\xa7\xc3\xa3o). O contador i \xc3\xa9 incrementado e a itera\xc3\xa7\xc3\xa3o continua. Em cada itera\xc3\xa7\xc3\xa3o, o algoritmo produzir\xc3\xa1 todas as permuta\xc3\xa7\xc3\xb5es que terminam com o elemento que acabou de ser movido para a "\xc3\xbaltima" posi\xc3\xa7\xc3\xa3o. O pseudoc\xc3\xb3digo a seguir produz todas as permuta\xc3\xa7\xc3\xb5es de um array de dados de comprimento N._NEWLINE_procedure generate(n : integer, A : array of any):_NEWLINE_    if n = 1 then_NEWLINE_          output(A)_NEWLINE_    else_NEWLINE_        for i := 0; i < n - 1; i += 1 do_NEWLINE_            generate(n - 1, A)_NEWLINE_            if n is even then_NEWLINE_                swap(A[i], A[n-1])_NEWLINE_            else_NEWLINE_                swap(A[0], A[n-1])_NEWLINE_            end if_NEWLINE_        end for_NEWLINE_    end if_NEWLINE_Este \xc3\xa9 o pseudoc\xc3\xb3digo para a vers\xc3\xa3o n\xc3\xa3o recursiva do algoritmo de Heap._NEWLINE_procedure generate(n : integer, A : array of any):_NEWLINE_    c : array of int_NEWLINE__NEWLINE_    for i := 0; i < n; i += 1 do_NEWLINE_        c[i] := 0_NEWLINE_    end for_NEWLINE__NEWLINE_    output(A)_NEWLINE__NEWLINE_    i := 0;_NEWLINE_    while i < n do_NEWLINE_        if  c[i] < i then_NEWLINE_            if i is even then_NEWLINE_                swap(A[0], A[i])_NEWLINE_            else_NEWLINE_                swap(A[c[i]], A[i])_NEWLINE_            end if_NEWLINE_            output(A)_NEWLINE_            c[i] += 1_NEWLINE_            i := 0_NEWLINE_        else_NEWLINE_            c[i] := 0_NEWLINE_            i += 1_NEWLINE_        end if_NEWLINE_    end while'