Pseudo Code de la méthode récursive d'impression Toutes les permutations de N $ N $ OPTERS

Question

Je ne comprends vraiment pas ce pseudo code.La fonction imprime toutes les permutations de N $ N $ comporte des entiers, en supposant que tous les numéros sont différents.

Y a-t-il un moyen d'expliquer ce code plus facilement car je n'ai vraiment pas le but de l'échange.

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

Votre procédure produit toutes les permutations de l'entrée, le renvoyant à son état d'origine à la fin.

Lorsque l'entrée a la longueur 1, il n'y a rien à faire.

Sinon, supposons que l'entrée soit $ a_1, \ ldots, a_n $ . Regardons toutes les permutations de $ a_1, \ ldots, a_n $ comme $ [A_1, \ ldots, a_n] $ < / span>.

Voici ce que la procédure fait:

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

Dans la première étape, la procédure passe simplement sur toutes les permutations de la queue de la liste, composée de tout sauf le premier élément.

dans la deuxième étape, il bascule $ a_1 $ et $ A_2 $ , passe sur toutes les permutations de la queue, puis change $ a_1 $ et $ a_2 $

dos.

dans la troisième étape, il bascule $ A_1 $ et $ A_3 $ , passe sur toutes les permutations de la queue, puis commutes $ a_1 $ et $ a_3 $

dos.

et ainsi de suite, jusqu'à ce que dans la $ N $ tre pas, il bascule $ A_1 $ et $ a_n $ , passe sur toutes les permutations de la queue, puis bascule $ A_1 $ et $ a_n $ retour.