Backtracking algorithm

Dev Shed Forums Sponsor:

March 11th, 2013, 03:16 PM

peter3110

Registered User

Join Date: Mar 2013

Posts: 7

Time spent in forums: 1 h 52 m 32 sec
Reputation Power: 0

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

salem

Contributed User

Join Date: Jun 2005

Posts: 3,840

Folding Points: 153 Folding Title: Novice Folder

Time spent in forums: 2 Months 3 Weeks 2 Days 19 h 19 m 34 sec
Reputation Power: 1774

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.

__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

March 18th, 2013, 09:27 AM

peter3110

Registered User

Join Date: Mar 2013

Posts: 7

Time spent in forums: 1 h 52 m 32 sec
Reputation Power: 0

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

Backtracking algorithm

Developer Shed Advertisers and Affiliates