2
$\begingroup$

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])
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.