CODEWITHSUNDEEP
javaalgorithmrecursionpermutationbacktracking
David
David

Reputation: 79

Permutation of string using backtracking algorithm

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

enter image description here

Upvotes: 4

Views: 4516

Answers (2)

Ramesh Varadarajan
Ramesh Varadarajan

Reputation: 1

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.

Upvotes: 0

Prune
Prune

Reputation: 77847

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?

Upvotes: 3

Related Questions