Pseudo Código de método recursivo para imprimir todas las permutaciones de $ n $ dados enteros

Question

Realmente no entiendo este pseudo código.La función imprime todas las permutaciones de $ n $ dados enteros, suponiendo que todos los números son diferentes.

¿Hay alguna manera de explicarle este código más fácilmente, ya que realmente no tengo el propósito del intercambio?

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

Su procedimiento produce todas las permutaciones de la entrada, devolviéndola a su estado original al final.

Cuando la entrada tiene longitud 1, no hay nada que hacer.

De lo contrario, suponga que la entrada es $ A_1, \ LDOTS, A_N $ . Permítanos representar todas las permutaciones de $ a_1, \ ldots, a_n $ como $ [A_1, \ LDOTS, A_N] $ < / span>.

Aquí es lo que hace el procedimiento:

• producción $ A_1, [A_2, A_3, \ LDOTS, A_ {N-1}, A_N] $ .
• producción $ A_2, [A_1, A_3, \ LDOTS, A_ {N-1}, A_N] $ .
• Salida $ A_3, [A_2, A_1, \ LDOTS, A_ {N-1}, A_N] $ .
• ...
• producción $ A_N, [A_2, A_3, \ LDOTS, A_ {N-1}, A_1] $ .

En el primer paso, el procedimiento simplemente pasa sobre todas las permutaciones de la cola de la lista, que consiste en todo menos el primer elemento.

En el segundo paso, cambia $ A_1 $ y $ A_2 $ , pasa por todas las permutaciones de la cola, y luego cambia $ A_1 $ y $ A_2 $ Atrás.

En el tercer paso, cambia $ A_1 $ y $ A_3 $ , pasa por todas las permutaciones de la cola, y luego cambia $ A_1 $ y $ A_3 $ Atrás.

y así sucesivamente, hasta que en el $ n $ th Step, cambia $ A_1 $ y $ a_n $ , pasa por todas las permutaciones de la cola, y luego cambia $ A_1 $ y $ A_N $ detrás.