You can try putting in some debug printf statements in your swap and permute functions at some key places to see what's being called/swapped. This will allow you to walk through and understand what's happening.
1) Calling Permute -
set = "abcd"
range > 1 [since 4-0]
for..
swaps(a,b) ???
No, "a" and "b" are not swapped, the first time through the for loop i is 0 and so what's swapped are "a" and "a" (since both begin and begin+i are 0). For this run, nothing is effectively done to the string.
2) Recursion on permute(set,1,4) --is it still abcd??
range>1
swap(b,d) ???
Yes, the string is still "abcd" when we call the permute function recursively, but remember that we are entering a new instance of the permute function with it's own set of local variables and arguments separate from the instance that we just came from. There exists an instance, the previous one, where begin is 0 and end is 4. In this new instance, begin is 1 and end is 4. Whenever the current instance ends and is popped off the stack, we return to the previous instance with whatever values that instance has for it's local variables and arguments. We may end up going many levels deep before finally popping all the instances of the function off the stack and exiting back to main.
Since we are in a new instance now, we again go into the for loop (i is still 0 since this is a new instance of the loop in a new instance of the function) and call the swap function. For this call, since i is still 0, we swap "b" with "b" since both begin and begin+i are 1. Again, nothing is modified in the string, it's still "abcd" at this point.
3)Recursion on permute(set,2,4) --is it still abcd??
range>1
swap(c,d) ???
The string is still "abcd" at the moment we call the permute function for the 3rd time (with begin 2 and end 4). We are now 3 levels deep into calling the function recursively. Again, we enter a new for loop with i starting out at 0 and we try and swap "c" and "c" (again, nothing happens to the string).
4)Recursion on permute(set,3,4) --is it still abcd??
range==1
print ??? What?
The string is still "abcd" when we call the function the 4th time with begin at 3 and end[/I] at 4. This time, when the range variable is checked and found to be 1 and we can finally print the string for the first time which is still "abcd". After this print, the 4th instance of the function gets popped off the stack and we are back to the 3rd instance (with begin 2 and end 4). The code reenters at the point just after the call to permute which is the call to the swap function. Since i is still 0 at this point, and begin and begin+i are both 2, we swap "c" and "c" which again do nothing (the string is still "abcd").
Finally we've reached the end of the for loop for this instance of the function and i gets incremented to 1. Now when we go back into the loop and execute the swap with begin 2 and begin+i 3, we actually swap "c" and "d" and the string gets modified to "abdc".
I'm not going to go any further than this, put in some print statements like I said and see for yourself what is happening. Try this and see what happens with the output:
Code:
void swap(char* src, char* dst)
{
static int i = 0;
printf("Swap(%03d): Swapping %c with %c,",++i,*src,*dst);
char ch = *dst;
*dst = *src;
*src = ch;
}
/* permute [set[begin], set[end]) */
int permute(char* set, int begin, int end)
{
int i;
int range = end - begin;
static int level = 0;
++level;
int this_level = level;
if (range == 1)
{
global++;
printf("\nPermute(%03d):set%d: %s\n\n",this_level,global,set);
}
else
{
for(i=0; i<range; i++)
{
swap(&set[begin], &set[begin+i]);
printf(" set string is now \"%s\".\n",set);
printf("Permute(%03d), i is %d, calling permute(\"%s\",%d,%d)\n",
this_level,i,set,begin+1,end);
permute(set, begin+1, end);
swap(&set[begin], &set[begin+i]); /* set back */
printf(" set string is now \"%s\".\n",set);
}
}
return 0;
}