Pseudocódigo do método recursivo de impressão de todas as permutações de $n$ dados inteiros

Question

Eu realmente não entendo esse pseudocódigo.A função imprime todas as permutações de $n$ dados inteiros, assumindo que todos os números são diferentes.

Existe uma maneira de explicar esse código com mais facilidade, já que realmente não entendi o propósito da troca.

PERMUTATE(A, start, end)
   if start == end return A
   else
      PERMUTATE(A,start+1,end)
      for i = start+1 to end
         SWAP(A[i],A[start])
         PERMUTATE(A,start+1,end)
         SWAP(A[start],A[i])

Answer 1

Seu procedimento produz todas as permutações da entrada, retornando-a ao seu estado original no final.

Quando a entrada tem comprimento 1, não há nada a fazer.

Caso contrário, suponha que a entrada seja $a_1,\ldots,a_n$.Vamos representar todas as permutações de $a_1,\ldots,a_n$ como $[a_1,\ldots,a_n]$.

Aqui está o que o procedimento faz:

• Saída $a_1,[a_2,a_3,\ldots,a_{n-1},a_n]$.
• Saída $a_2,[a_1,a_3,\ldots,a_{n-1},a_n]$.
• Saída $a_3,[a_2,a_1,\ldots,a_{n-1},a_n]$.
• ...
• Saída $a_n,[a_2,a_3,\ldots,a_{n-1},a_1]$.

Na primeira etapa, o procedimento apenas percorre todas as permutações da cauda da lista, consistindo em todos, exceto no primeiro elemento.

Na segunda etapa, ele muda $a_1$ e $a_2$, repassa todas as permutações da cauda e depois muda $a_1$ e $a_2$ voltar.

Na terceira etapa, ele muda $a_1$ e $a_3$, repassa todas as permutações da cauda e depois muda $a_1$ e $a_3$ voltar.

E assim por diante, até que no $n$º passo, ele muda $a_1$ e $a_n$, repassa todas as permutações da cauda e depois muda $a_1$ e $a_n$ voltar.