mercredi 5 août 2015

String permutation - How does this backtracking recursion work?


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
       }
   }
}



via Chebli Mohamed

Aucun commentaire:

Enregistrer un commentaire