Efficient String permutations calculation in Java

Question

In trying to compute permutations of a given String, what can I do to further improve the code below for memory and/or time efficiency?

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        permutateString("ABC");
    }

    private static void permutateString(String str) {

        List<String> results = permutations(new StringBuilder(str), new ArrayList<>());
        System.out.println("Number of permutations: " + results.size()
                            + "\n" + "Permutations: \n" + results);
    }

    private static List<String> permutations(StringBuilder input, List<String> permutationsList) {

        if (input.length() == 0 || input.length() == 1) {
            permutationsList.add(input.toString());
        }
        else {
            char prefix;
            StringBuilder substring;

            for (int i=0; i<input.length(); i++) {
                prefix = input.charAt(i);
                substring = new StringBuilder(input).deleteCharAt(i);
                for (String str : permutations(substring, new ArrayList<>())) {
                    permutationsList.add(String.valueOf(prefix) + str);
                }
            }
        }
        return permutationsList;
    }
}

Answer 1

Why are you giving as parameter to permutations a permutationsList, that you will both mutate and return? The purpose of this method is to generate the permutations of the given input; it shouldn't need to take any list as parameter, and should just return the result. (Also, node that this method is only called by giving it a new array list, which hints that it isn't really needed).

Also, why does it take a StringBuilder as parameter? This method doesn't try build a String with it, it just get its length and the character at a given index. So pass it a String.

Therefore, consider this instead:

private static List<String> permutations(String input) {
    List<String> permutationsList = new ArrayList<>();
    // ...
    return permutationsList;
}

And with this small change, we can clarify the code more. We would have

List<String> permutationsList = new ArrayList<>();
if (input.length() == 0 || input.length() == 1) {
    permutationsList.add(input);
} else {
    // ...
}
return permutationsList;

(We don't need to call toString() anymore since the argument is now a String). The first part handles the base condition of the recursion. Notice that it builds a new list, only to add a single element to it and return it directly. Instead, we can use the optimized Collections.singletonList(o) which directly returns a list containing the single given element. Now we can have:

if (input.length() == 0 || input.length() == 1) {
    return Collections.singletonList(input);
}
List<String> permutationsList = new ArrayList<>();
// ...
return permutationsList;

No need for an else-clause, and the use of the early return saves one level of indentation and adds to clarity.

Then, we can move on to the scope of the variables. So far, the code is:

char prefix;
StringBuilder substring;
for (int i=0; i<input.length(); i++) {
    prefix = input.charAt(i);
    substring = new StringBuilder(input).deleteCharAt(i);
    // ...
}

Why declare the variables outside of the for loop? They are only used inside of it; variables should have the tighter scope possible. Instead, consider:

for (int i=0; i<input.length(); i++) {
    char prefix = input.charAt(i);
    StringBuilder substring = new StringBuilder(input).deleteCharAt(i);
    // ...
}

which saves in lines of code, makes sure prefix and substring have a minimal scope and is overall clearer.

Finally, the inner for loop calculates String.valueOf(prefix) each time, when the result will always be the same.

char prefix = input.charAt(i);
// ...
for (String str : permutations(substring)) {
    permutationsList.add(String.valueOf(prefix) + str);
}

This could be done a single time and reuse the result with

String prefix = String.valueOf(input.charAt(i));
// ...
for (String str : permutations(substring)) {
    permutationsList.add(prefix + str);
}

With all that, the end result is:

private static List<String> permutations(String input) {
    if (input.length() == 0 || input.length() == 1) {
        return Collections.singletonList(input);
    }
    List<String> permutationsList = new ArrayList<>();
    for (int i = 0; i < input.length(); i++) {
        String prefix = String.valueOf(input.charAt(i));
        String substring = new StringBuilder(input).deleteCharAt(i).toString();
        for (String str : permutations(substring)) {
            permutationsList.add(prefix + str);
        }
    }
    return permutationsList;
}

Other comments:

• permutateString is a wrong name. The word "permutate" doesn't exist, it should be "permute". But actually, even that would be a wrong name: the method doesn't actually permute the given String. It prints the permutations of it. The difference is that, with a method named permuteString, one would expect it to return the permutations, except this one doesn't, since it prints them. Consider renaming it printPermutationsOf.
• If you worry about the memory and time efficiency of the algorithm, then you're likely not using the right tool here. Building all the permutations will be memory intensive (with all the objects to build), and very slow (complexity is O(n!), where n is the length of the String). It is only practical for short Strings: there are already more than 3 millions permutations for a String of length 10. Depending on the use-case, you will either want to filter some of them, or even use a completely different approach that doesn't require building any permutations.