Permutations of a String in Java

1. Introduction

A permutation is the rearrangement of elements in a set. In other words, it is all the possible variations of the collection order.

In this tutorial, we’ll learn how we can easily create permutations in Java using third-party libraries. More specifically, we’ll be working with permutations in a String.

2. Permutations

Sometimes, we need to check all the possible permutations of a String value, often for mind-boggling online coding exercises and less often for day-to-day work tasks. For example, a String “abc” will have six different ways to arrange the characters inside: “abc”, “acb”, “cab”, “bac”, “bca”, “cba”.

A couple of well-defined algorithms can help us create all the possible permutations for a particular String value. For example, the most famous is Heap’s algorithm. However, it’s pretty complex and non-intuitive. The recursive approach, on top of this, makes matters worse.

3. Elegant Solution

Implementing an algorithm for generating permutations will require writing custom logic. It’s easy to make a mistake in the implementation and hard to test that it works correctly over time. Also, there is no sense in rewriting the things written before.

Additionally, when working with String values, it’s possible to flood the String pool by creating too many instances if not doing it carefully.

Here are libraries that currently provide such functionality:

• Apache Commons
• Guava
• CombinatoricsLib

Let’s try to find all the permutations for a String value using these libraries. We’ll be paying attention to whether these libraries allow lazy traverse over permutations and how they handle duplicates in the input value.

We’ll use the Helper.toCharacterList method in the examples below. This method encapsulates the complexity of converting a String to the List of Characters:

static List<Character> toCharacterList(final String string) {
    return string.chars().mapToObj(s -> ((char) s)).collect(Collectors.toList());
}

Also, we’ll be using a helper method to convert a List of Characters to a String:

static String toString(Collection<Character> collection) {
    return collection.stream().map(s -> s.toString()).collect(Collectors.joining());
}

4. Apache Commons

First, let’s add the Maven dependency commons-collections4 to the project:

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-collections4</artifactId>
    <version>4.5.0-M2</version>
</dependency>

Overall, Apache provides a simple API. CollectionUtils creates permutations eagerly, so we should be careful when working with long String values:

public List<String> eagerPermutationWithRepetitions(final String string) {
    final List<Character> characters = Helper.toCharacterList(string);
    return CollectionUtils.permutations(characters)
        .stream()
        .map(Helper::toString)
        .collect(Collectors.toList());
}

At the same time, to make it work with a lazy approach, we should use PermutationIterator:

public List<String> lazyPermutationWithoutRepetitions(final String string) {
    final List<Character> characters = Helper.toCharacterList(string);
    final PermutationIterator<Character> permutationIterator = new PermutationIterator<>(characters);
    final List<String> result = new ArrayList<>();
    while (permutationIterator.hasNext()) {
        result.add(Helper.toString(permutationIterator.next()));
    }
    return result;
}

This library doesn’t handle duplicates, so the String “aaaaaa” will produce 720 permutations, which is often not desirable. Also, PermutationIterator doesn’t have a method to get the number of permutations. In this case, we should calculate them separately based on the input size.

5. Guava

First, let’s add the Maven dependency for the Guava library to the project:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>33.0.0-jre</version>
</dependency>

Guava allows the creation of permutations with Collections2. The API is straightforward to use:

public List<String> permutationWithRepetitions(final String string) {
    final List<Character> characters = Helper.toCharacterList(string);
    return Collections2.permutations(characters).stream()
        .map(Helper::toString)
        .collect(Collectors.toList());
}

The result of Collections2.permutations is a PermutationCollection, which allows easy access to permutations. All the permutations are created lazily.

Additionally, this class provides an API for creating permutations without repetitions:

public List<String> permutationWithoutRepetitions(final String string) {
    final List<Character> characters = Helper.toCharacterList(string);
    return Collections2.orderedPermutations(characters).stream()
        .map(Helper::toString)
        .collect(Collectors.toList());
}

However, the problem with these methods is that they’re annotated with @Beta annotation, which doesn’t guarantee that this API won’t change in future releases.

6. CombinatoricsLib

To use it in the project, let’s add the combinatoricslib3 Maven dependency:

<dependency>
    <groupId>com.github.dpaukov</groupId>
    <artifactId>combinatoricslib3</artifactId>
    <version>3.3.3</version>
</dependency>

Although this is a small library, it provides many combinatorics tools, including permutations. The API itself is very intuitive and utilizes Java streams. Let’s create permutations from a particular String or a List of Characters:

public List<String> permutationWithoutRepetitions(final String string) {
    List<Character> chars = Helper.toCharacterList(string);
    return Generator.permutation(chars)
      .simple()
      .stream()
      .map(Helper::toString)
      .collect(Collectors.toList());
}

The code above creates a generator that will provide the permutations for the String. Permutation will be retrieved lazily. Thus, we only created a generator and calculated the expected number of permutations.

At the same time, with this library, we can identify the strategy for duplicates. If we use a String “aaaaaa” as an example, we will get only one instead of 720 identical permutations.

public List<String> permutationWithRepetitions(final String string) {
    List<Character> chars = Helper.toCharacterList(string);
    return Generator.permutation(chars)
      .simple(TreatDuplicatesAs.IDENTICAL)
      .stream()
      .map(Helper::toString)
      .collect(Collectors.toList());
}

TreatDuplicatesAs allows us to define how we would like to treat duplicates.

7. Conclusion

There are plenty of ways to deal with combinatorics and permutations in particular. All of these libraries can help significantly with this. It is worth trying all of them and deciding which one fits your needs. Although many people are urged to write all of their code sometimes, it doesn’t make sense to waste time on something that is already there and provides good functionality.