Permutation of string using backtracking algorithm

Question

I was reading the code below on Geeksforgeeks, but I just can't wrap my head around how it works! If anyone can explain it pictorially. That'd be great!

this is the code:

static void swap(char a[], int l, int r) {
    char temp = a[l];
    a[l] = a[r];
    a[r] = temp;
}

static void permute(char a[], int l, int r) {
    if (l == r)
        System.out.println(getString(a));
    else {
        for (int i = l; i <= r; i++) {
            swap(a, l, i);
            permute(a, l + 1, r);
            swap(a, l, i); // backtrack
        }
    }
}

Prune · Accepted Answer · 2016-02-18 00:46:32Z

3

I don't see where you're confused: you provided a picture that explains it quite clearly ... to me. :-)

Termination condition (bottom row of your diagram, 2 red & 1 green items): if the list has only one remaining element to consider, there's nowhere to swap it. The permutation is done. return

Otherwise ... For each item remaining in the array, swap that position into the left-most available spot. Move the "fixed" pointer one spot to the right, and call the routine on the rest of the array.

Overall, this simply walks down the array: pick each item (in turn) for the first position; pick each remaining item (in turn) for the second; ... continue through the end of the list.

Does that clear up anything for you?

answered Feb 18, 2016 at 0:46

Prune

78k14 gold badges63 silver badges83 bronze badges

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

3 Comments

David Over a year ago

I've tried to trace the logic, but it often gets messed up. =(

Prune Over a year ago

"it often gets messed up" is not a problem description. Please see how to ask. Until you can tell us where and how you have a problem, we cannot effectively help you.

David Over a year ago

I see, next time I know.

Ramesh Varadarajan · Accepted Answer · 2023-07-30 04:46:51Z

You have not included the driver code where the function is executed namely permute(a[],0,len) where len is the length of the string. Start with l=0 and r=len and trace the code with the help of the diagram. Read the swap statement along each arrow in the diagram. The technique used is called backtracking an important data structure concept called depth first search. (The 2 swap statements are used to return to where you started after you have explored each branch to the bottom). You start at the top and go all the way down the left till you reach the bottom left. Then go one step upwards and do the next left leaf (in this case there are 3 leaves for each source node) until the rightmost leaf is reached at each level. (Here you have 3 levels) It is somewhat intriguing, but the diagram is the simplest possible. Hope this helps but requires considerable self-help.

Collectives™ on Stack Overflow

Permutation of string using backtracking algorithm

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related