2

This function basically prints all possible permutations of a string by swapping a character with all its other characters. I understand the first two calls to swap and permute. But why is swap called for the second time? I cannot understand this piece of code. Can someone please explain me how this works?

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}
Joy Rex
  • 608
  • 7
  • 32
Tania
  • 1,855
  • 1
  • 15
  • 38

1 Answers1

3

The "backtrack" swaps the string back to its original state, which is vital for the correct running of the algorithm.

You wouldn't want your function to mess up your input string, would you?

Bathsheba
  • 231,907
  • 34
  • 361
  • 483
  • 2
    Not only to preserve input, but also to avoid duplicates and other weird behavior. We want to make sure to leave it intact so that the previous call finds the character in the same place. – Filipe Gonçalves Aug 04 '15 at 13:50
  • @FilipeGonçalves: very true, on second reading there was an implication that I was suggesting it was only an "ettiquette" call, which of course it isn't. – Bathsheba Aug 04 '15 at 13:58