Pseudo Codice del metodo ricorsivo per la stampa di tutte le permutazioni di $ N $ dati interi

Question

Non capisco davvero questo codice pseudo.La funzione stampa tutte le permutazioni di $ N $ Dato interi, supponendo che tutti i numeri siano diversi.

C'è un modo per spiegare questo codice più facilmente poiché davvero non ottengo lo scopo dello scambio.

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

La tua procedura produce tutte le permutazioni dell'input, rendendolo al suo stato originale alla fine.

Quando l'ingresso ha lunghezza 1, non c'è nulla da fare.

Altrimenti, supponiamo che l'ingresso sia $ a_1, \ ldots, a_n $ . Rappreentiamo tutte le permutazioni di $ a_1, \ ldots, a_n $ come $ [A_1, \ LDOTS, A_N] $ < / span>.

Ecco cosa è la procedura:

.
• output $ A_1, [A_2, A_3, \ LDOTS, A_ {N-1}, A_N] $ .
• Output $ A_2, [A_1, A_3, \ LDOTS, A_ {N-1}, A_N] $ .
• OUTPUT $ A_3, [A_2, A_1, \ LDOTS, A_ {N-1}, A_N] $ .
• ...
• output $ a_n, [A_2, A_3, \ LDOTS, A_ {N-1}, A_1] $ .

Nel primo passo, la procedura va solo su tutte le permutazioni della coda della lista, costituita da tutti tranne il primo elemento.

Nel secondo passo, cambia $ A_1 $ e $ A_2 $ , supera tutte le permutazioni della coda, quindi cambia $ A_1 $ e $ A_2 $ indietro.

Nel terzo passo, cambia $ a_1 $ e $ A_3 $ , supera tutte le permutazioni della coda, quindi commuta $ A_1 $ e $ a_3 $ indietro.

E così via, fino a quando nella $ N $ passo, passa $ a_1 $ e $ a_n $ , va su tutte le permutazioni della coda, quindi cambia $ A_1 $ e $ a_n $ indietro.