Creates all possible permutations of a string and its substrings

Question

I want to improve this code to efficiently create all possible permutations/combinations of a string. For example, if I have the string "abc", the result would be the list [ab, ac, ba, bc, ca, cb, abc, acb ...]. I have a solution for this but it takes too long on larger inputs. I need help with improving its efficiency and speed.

The working code is below that I want to improve. Here's what it's doing:

It takes the input string and keeps adding the permutations to the permutations list. It loops through that list until the end. In the loop, it keeps adding new permutations to the permutations list so it keeps growing until we don't have any more permutations left and eventually, we reach the end of the list.

Example:

We have "abc" as the input string.

permutations list initialized to [a, b, c].

What the loop does

• a * bc -> ab, ac ('a' is permutaions[i] and 'bc' is what getMultiplicand(...) returned)

  permutations -> [a, b, c, ab, ac]

• b * ac -> ba, bc

  permutations -> [a, b, c, ab, ac, ba, bc]

• c * ab -> ca, cb

  permutations -> [a, b, c, ab, ac, ba, bc, ca, cb]

• ab * c -> abc

  permutations -> [a, b, c, ab, ac, ba, bc, ca, cb, abc]

• ac * b -> acb

  permutations -> [a, b, c, ab, ac, ba, bc, ca, cb, abc, acb]

And so on...

At the end of the loop permutations is converted to a Set containing all unique possible combinations of the input string.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class Test {

    private Set<String> permute(String charSeq) {
        long starttime = System.nanoTime();
        List<String> permutations = new ArrayList<>();
        // Add each character from the string to get us going for multiplication. We'll remove them at the very end.
        for (int i = 0; i < charSeq.length(); i++) {
            permutations.add(String.valueOf(charSeq.charAt(i)));
        }
        // This list will be used to hold the permutations produced by each iteration.
        List<String> tempPermutation = new ArrayList<>();
        for (int i = 0; i < permutations.size(); i++) {
            Character[] multiplicand = getMultiplicand(charSeq, permutations.get(i));
            for (Character character: multiplicand) {
                tempPermutation.add(permutations.get(i) + character);
            }
            // Merge the temporary permutations list with the main permutations list and then clear it for the next iteration.
            permutations.addAll(tempPermutation);
            tempPermutation.clear();
        }
        // Remove the single characters we added at the very beginning
        for (int i = 0; i < charSeq.length(); i++) {
            permutations.remove(String.valueOf(charSeq.charAt(i)));
        }
        // Convert the permutations list into a set to remove all the duplicates.
        return new HashSet<>(permutations);
    }

    private Character[] getMultiplicand(String s, String toRemove) {
        List<Character> characters = s.chars().mapToObj(c -> (char) c).collect(Collectors.toList());
        for (int i = 0; i < toRemove.length(); i++) {
            characters.remove(Character.valueOf(toRemove.charAt(i)));
        }
        return characters.toArray(new Character[0]);
    }
}

P.S. This is my first post so tell me how it can be improved. Thanks.

Answer 1

Permutations are the kind of problem that quickly generate an incredible amount of data. Collecting them all into a "big bag" before returning them all at once becomes unfeasible. Instead use a simple producer-consumer design pattern: pass an instance of Consumer<String> as a parameter to the method and whenever you have a permutation ready, call the consumer immediately and let them handle the processing and storage of the reults.

I'm not going to go into your code, because I think it starts off with the wrong approach. Creating premutations is naturally a very simple recursive algorithm: you pick an item from the data set and append it to all permutations of the rest of the data. There are a lot of examples in the internet about this. Unless you specifically want to write an iterative version of the algorithm, I would recommend that you scrap the code, take a look how the recursive algorithm should be written and then completely rewrite your own.

Regarding performance, object allocation is what kills Java. Usually it is because the programmer does not understand how the underlying standard libraries work and unknowingly end up creating a lot of "single use" throwaway objects. If you tweak your code so that you don't need to generate any objects, the actual algorithm is equally fast to a C implementation. I just recently wrote a utility class for creating combinations from a collection and during the execution of the algorithm, you shouldn't need to have to create new objects for any other reason than returning the result to the consumer.