#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    7
    Rep 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;
    }
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,387
    Rep Power
    1871
    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
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    7
    Rep 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 :D

IMN logo majestic logo threadwatch logo seochat tools logo