Not able to understand string permutation Java code

Question

I have this working code to print string permutations without repetitions, but not able to wrap my head around how is it working as in logic. Any suggestions will be really helpful.

private static void permutation(String input, String sofar) {
        if (input.equals("")) {
            System.out.println(count + " " + sofar);
            count++;
        }
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (input.indexOf(c, i + 1) != -1)
                continue;
            permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);
        }
    }

Function call:

String input = "ABBCD";
permutation(input, "");

Tried . but still not able to make sense. Recursive calls are driving me crazy. So, I am hoping if someone can say what is being done here on broad level in few lines. That will be very kind. — Walt, Feb 05 '15 at 17:15
re write it to be iterative. Any recursive algorithm can be implemented iteratively — thermite, Feb 05 '15 at 17:20
possible duplicate of [Generating all permutations of a given string](http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string) — , Feb 05 '15 at 17:23

score 3 · Accepted Answer · answered Feb 05 '15 at 17:23

3

 for (int i = 0; i < input.length(); i++) {

The above for loop is doing the magic

Input ABCD

Iterations

input: BCD sofar: A .... recursion goes on

input: ACD sofar: B ....

input: ABD sofar: C ....

input: ABC sofar: D .....

Hope this helps

answered Feb 05 '15 at 17:23

Andy897

6,915
11
51
86

Precisely this is what I was missing. Stupidity at its best. :( – Walt Feb 05 '15 at 17:25
1

There is a bit more to it than just that. – Reut Sharabani Feb 05 '15 at 17:40

Reut Sharabani · Answer 2 · 2015-02-05T17:54:48.793

Just remember that recursion is usually a stop condition, and an attempt to solve a smaller problem using the recursive call, under the assumption that the recursion works.

I've commented the code so you can replace that with your copy to keep track of what it's doing when you get back to it. Add your own comments once you understand as they'll help you follow what happens:

Part 1: The basic condition / stop condition:

if (input.equals("")) {
    System.out.println(count + " " + sofar);
    count++;
}

This part stops the recursion and returns a result, the base case being an empty string, which has a single permutation that is also an empty string.

Part 2: Iterating smaller problems.

 for (int i = 0; i < input.length(); i++) {
    char c = input.charAt(i);
    // ...
    permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);
}

This part uses the recursive call on a smaller (by one character) string, to solve the problem. It calls the same string omitting a character it prepends to whatever following results it generates. We know the call generates all permutations (that's our assumption). So we now know what the recursion does.

Part 2.1: The de-duplicating "if":

This is probably the trickiest part here...

if (input.indexOf(c, i + 1) != -1)
    continue;

Let's figure this out. What it means, is: "try and find a character the same as the one selected, and if one exists, skip this iteration and it's generated solutions".

Think of a word like "ABBA" it will skip the first "A" and "B", but not the last ones. Why? Well, since order of similar characters does not matter (if we tag the character A1 B1 B2 A2, and now replace them: A2 B2 B1 A1, this is still the same word, so there is only one permutation for words like "AA", since A1 A2 is the same as A2 A1.

Taking the last characters is easier, since we don't need to maintain a list of the characters we already used in this iteration.

The full code with basic comments:

private static void permutation(String input, String sofar) {

        if (input.equals("")) {
            // this is the stop condition
            // the only permutation of "" is ""
            System.out.println(count + " " + sofar);
            // this counts how many permutations were outputted.
            count++;
        }

        for (int i = 0; i < input.length(); i++) {
            // this loop basically means "take every
            // possible character, and append permutations of all
            // other characters to it.
            char c = input.charAt(i);
            if (input.indexOf(c, i + 1) != -1)
                // this makes sure we only take a single "A" or "B"
                // character in words like "ABBA", since selecting
                // the same character would create duplicates
                continue;

            // this creates a new string without the selected character
            // and under the assumption the recursion works
            // appends all permutations of all other characters
            // to it
            permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);
        }
    }

score 1 · Answer 3 · answered Feb 05 '15 at 17:23

if (input.equals("")) {
     System.out.println(count + " " + sofar);
     count++;
}

This step is passed as the input is not "". Note that you could simply use input.empty() here. The only thing to remember here is that count have not been incremented.

for (int i = 0; i < input.length(); i++) {

This will, loop over all character of the input

char c = input.charAt(i);
if (input.indexOf(c, i + 1) != -1)

This check if the next character is equal to the current one, if it does then it will jump directly to the next iteration(the next character) using the continue keyword.

If it does not, then it will recall the method (We call that recursivity), passing in the string without the current char. But giving it back to sofar.

permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);

Now in the case where input is empty,

The count of non-distinct character will be printed + all these character.

Not able to understand string permutation Java code

3 Answers3

Linked

Related