March 11th, 2013, 03:16 PM
-
Backtracking algorithm
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
Code:
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
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;
}
March 12th, 2013, 12:08 AM
-
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.
Code:
$ 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.
March 18th, 2013, 09:27 AM
-
thank you
thank you very much, after a whole day of trying to think like a computer i finally understood the mechanics of the algorithm :D