Pseudo code of recursive method of printing all permutations of $n$ given integers

Question

I really don't understand this pseudo code. The function prints all permutations of $n$ given integers, assuming that all numbers are different.

Is there a way to explain this code more easily as I really don't get the purpose of the swapping.

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

Your procedure produces all permutations of the input, returning it to its original state at the end.

When the input has length 1, there is nothing to do.

Otherwise, suppose that the input is $a_1,\ldots,a_n$. Let us represent all permutations of $a_1,\ldots,a_n$ as $[a_1,\ldots,a_n]$.

Here is what the procedure does:

• 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]$.

In the first step, the procedure just goes over all permutations of the tail of the list, consisting of all but the first element.

In the second step, it switches $a_1$ and $a_2$, goes over all permutations of the tail, and then switches $a_1$ and $a_2$ back.

In the third step, it switches $a_1$ and $a_3$, goes over all permutations of the tail, and then switches $a_1$ and $a_3$ back.

And so on, until in the $n$th step, it switches $a_1$ and $a_n$, goes over all permutations of the tail, and then switches $a_1$ and $a_n$ back.