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. 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.
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:
(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.
3. 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