-2

I was given a task of writing a program for string permutation. I understand the logic, but not the exact meaning of the Backtrack in this program. Please explain the for-loop functionality, when swap will be called, when permutate() will be called, and the exact meaning of backtrack.

# include <stdio.h>


void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}


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
       }
   }
} 


int main()
{
   char a[] = "ABC";  
   permute(a, 0, 2);
   getchar();
   return 0;
}
Improve this question
9
  • 5
    This question appears to be off-topic because it is about algorithm theory and not about programming. Commented Oct 7, 2013 at 8:35
  • From where you got CODE,there you will understand meaning of all. :) Commented Oct 7, 2013 at 8:37
  • @KerrekSB is there any place to ask these type of question ? I wanna ask the logic in for loop . how it is working ? Commented Oct 7, 2013 at 8:38
  • @Purisima There is no explanation of that , some one had written the code only Commented Oct 7, 2013 at 8:40
  • 1
    Personally I would not describe that as backtracking. Backtracking is where you try for a solution one way, realise it's not working and then go back (backtrack) to an earlier point and try something else. All the line marked backtrack does is undo the change made two lines earlier. Commented Oct 7, 2013 at 8:42

2 Answers 2

Reset to default
0

Sketching the call stack can help you understanding how the algorithm works. The example string "ABC" is a good starting point. Basically, this is what will happen with ABC:

permute(ABC, 0, 2)
    i = 0
    j = 0
    permute(ABC, 1, 2)
        i = 1
        j = 1
        permute(ABC, 2, 2)
            print "ABC"
        j = 2
        string = ACB
        permute(ACB, 2, 2)
            print "ACB"
        string = ABC
    j = 1
    string = BAC
    permute(BAC, 1, 2)
        .... (everything starts over)

As usual, in the example above, indentation defines what happens inside each of the recursive calls.

The reasoning behind the for loop is that every permutation of string ABC is given by ABC, BAC and CBA, plus every permutation of the substrings BC, AC and BA (remove the first letter from each of the previous ones). For any string S, the possible permutations are obtained by swapping every position with the first one, plus all of the permutations of each of these strings. Think of it like this: any permuted string must start with one of the letters in the original string, so you place every possible letter in the first position, and recursively apply the same method to the rest of the string (without the first letter).

That's what the loop is doing: we scan the string from the current starting point (which is i) up to the end, and at each step we swap that position with the starting point, recursively call permute() to print every permutation of this new string, and after that we restore the string back to its previous state, so that we have the original string to repeat the same process with the next position.

Personally, I don't like that comment saying "backtrack". A better term would be "winding back", because at that point the recursion winds back and you prepare your string for the next recursive call. Backtrack is normally used for a situation in which you explored a subtree and you didn't find a solution, so you go back up (backtrack) and try a different branch. Taken from wikipedia:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

Note that this algorithm does not generate the set of permutations, because it can print the same string more than once when there are repeated letters. An extreme case is when you apply it to the string "aaaaa", or any other string with one unique letter.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

"Backtracking" means, you are gong back one step in your solution space (think of it as a decision tree and you are going up one level). It is usually used if you can rule out certain sub-trees in the decision space, and gives significant performance boost compared to full exploration of the decision tree if and only if it is very likely that you can rule out larger parts of the solution space.

You can find an exhaustive expalnation of a similar algorithm here: Using recursion and backtracking to generate all possible combinations

Improve this answer

3 Comments

What you describe is branch and bound not backtracking. en.wikipedia.org/wiki/Branch_and_bound. A branch-and-bound algorithm consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded **en masse**, by using upper and lower estimated bounds of the quantity being optimized.
no, branch and bound is about eleminating fruitless candidates en masse, by using upper and lower estimated bounds - which is something different then the description in my anwer. (you don't need estimation bounds in backtracking)
You're right, I misunderstood some part of your answer.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.