Need explanation for permutations of a string using recursion...code is in thread

[arsenal_fan]

Hi,

I got this code for computing permutations of a string from the programming interviews exposed book. I am unable to think as to how recursion works in this case. Now, if the input string is "hat", then I have understood the sequence of recursive calls that lead to the printing of hat but am unable to figure out anything after that i.e. which statement is executed after returning from the recursive call. Could anyone help me understand this code?

int permutations(char *str)
{
  int length, i, *used;
  char *out;

  length = strlen(str);
  out = (char *)malloc(length+1);
  if(!out)
    return 0;

  out[length] = '\0';
  used = (int*)malloc(sizeof(int)*length);
  if(!used)
    return 0;

  for(i=0;i<length;i++)
    used[i]=0;

  DoPermute(str, out, used, length, 0);
  
  free(out);
  free(used);
  return 1;

}

void DoPermute(char *str, char* out, int* used, int length, int recursLev)
{
  int i;

  if(recursLev==length)
    {
      printf("%s\n", out);
      return;
    }

  for(i=0;i<length;i++)
    {
      if(used[i])
	continue;

      out[recursLev] = str[i];
      used[i] = 1;
      DoPermute(str, out, used, length, recursLev+1);
      used[i]=0;
    }
}

Thanks all.

[Ancient Dragon]

>>which statement is executed after returning from the recursive call.

Line 45, then the loop continues, but at that point the value of i is the value of length - because lines 39 and 40 advance i to the end of the output string before doing any recursion.

[arsenal_fan]

Hi Ancient Dragon,

Thanks for the reply. I am finding a hard time trying to explain what I am not able to understand since I am not able to clearly imagine how the sequence of recursive calls work. Anyway, this is how I think the sequence goes:

With input "hat",
1. value of i =0, out[0] = 'h', used[0]=1, recursive call (I assume i=0, recursLev =0, is pushed on to the stack)
2. i =0 continue, i=1 out[1]='a', used[1] = 1, recursive call (i =1, recurseLev =1 on stack)
3. i=0,1 continue, i=1 out[2] = 't', used[2] = 1, recursive call(i=2, recurseLev=2 on stack)
4. Line 31 is executed, "hat" is printed out and it returns.

It is from here that I am confused. This is what I think happens:

5. Return to line 45, pop i from stack, used[2]=0, i incremented to 3, break out of the loop.

Could you like trace it from here for 1 run? I just want to be clear in my head as to how these recursive calls work?

I mean the way I think this code works is: print out the first character and then permute the other 2 i.e. "h" and permute "at" to get "hat" and "hta" respectively. What I also cannot figure out is where the swapping of characters a and t is done to output "hta"?

Thanks again for all your help.

[Ancient Dragon]

you have two options to trace that program

1. Learn to use your compiler's debugger and step through the program one statement at a time so that you can see how it is executed.
2. Put some print statements in that code.

>>What I also cannot figure out is where the swapping of characters a and t is done to output "hta"?
That's because the chracters are not swapped.