[peter3110]

hi, i've been able to found an algorithm which calculates and outputs all the permutations of a given word. I can´t understand how is it that all the permutations print themselves, and when is it that they do it

permute (i)

if (i==N) output A[N]
else 
     for j=i to N do 
         swap (A[i], A[j])
         permute (i+1)
         swap (A[i], A[j]) //backtrack (??)

I mean, for the program to output something, i don't see any other option but that the word to be permuted to have only one word.
I have tried to follow each step of the program as if i were the computer but still couldn't get it.

and here is the complete code

# include <stdio.h>
 
/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
  
/* 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 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)); //backtrack
       }
   }
} 
 
/* Driver program to test above functions */
int main()
{
   char a[] = "CASA";  
   permute(a, 0, 3);
   return 0;
}

[salem]

Use a debugger (or add some extra printf statements) to examine in detail what is going on.

Use test strings starting with "A" then "AB" then "ABC".

Eg.

$ gcc -g foo.c
$ gdb ./a.out 
GNU gdb (Ubuntu/Linaro 7.3-0ubuntu2) 7.3-2011.08
Copyright (C) 2011 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
For bug reporting instructions, please see:
<http://bugs.launchpad.net/gdb-linaro/>...
Reading symbols from /home/sc/Documents/a.out...done.
(gdb) break permute 
Breakpoint 1 at 0x4005a5: file foo.c, line 20.
(gdb) run
Starting program: /home/sc/Documents/a.out 

Breakpoint 1, permute (a=0x7fffffffe180 "ABC", i=0, n=2) at foo.c:20
20	   if (i == n)
(gdb) cont
Continuing.

Breakpoint 1, permute (a=0x7fffffffe180 "ABC", i=1, n=2) at foo.c:20
20	   if (i == n)
(gdb) 
Continuing.

Breakpoint 1, permute (a=0x7fffffffe180 "ABC", i=2, n=2) at foo.c:20
20	   if (i == n)
(gdb) 
Continuing.
ABC

Breakpoint 1, permute (a=0x7fffffffe180 "ACB", i=2, n=2) at foo.c:20
20	   if (i == n)
(gdb) 
Continuing.
ACB

Breakpoint 1, permute (a=0x7fffffffe180 "BAC", i=1, n=2) at foo.c:20
20	   if (i == n)
(gdb)

Follow this through, see how the parameters change.

[peter3110]

thank you very much, after a whole day of trying to think like a computer i finally understood the mechanics of the algorithm :D