Print all the permutations of a string in C

Question

I am learning backtracking and recursion and I am stuck at an algorithm for printing all the permutations of a string. I solved it using the bell algorithm for permutation but I am not able to understand the recursion method. I searched the web and found this code:

void permute(char *a, int i, int n) 
{
   int j; 
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); 
       }
   }
} 

How is this algorithm basically working I am unable to understand? I even tried dry running!

How is the backtracking applied?

And is it more efficient than the Bell Algorithm for calculation of permutation?

Answer 1

The algorithm basically works on this logic:

All permutations of a string X is the same thing as all permutations of each possible character in X, combined with all permutations of the string X without that letter in it.

That is to say, all permutations of "abcd" are

• "a" concatenated with all permutations of "bcd"
• "b" concatenated with all permutations of "acd"
• "c" concatenated with all permutations of "bad"
• "d" concatenated with all permutations of "bca"

This algorithm in particular instead of performing recursion on substrings, performs the recursion in place on the input string, using up no additional memory for allocating substrings. The "backtracking" undoes the changes to the string, leaving it in its original state.