## 1.绪论

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

permutation是对一个集合中的元素进行重新排列。换句话说，它是集合顺序的所有可能变化。

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 permutation in a String.

## 2.排列组合

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.优雅的解决方案

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, working with String values, it’s possible to flood the String pool by creating too many instances if not doing it carefully.

Here’re 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 if these libraries allow lazy traverse over permutations and how they handle duplicates in the input value.

We’ll use an 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.阿帕奇公社

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

<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-collections4</artifactId>
<version>4.4</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()) {
}
return result;
}

This library doesn’t handle duplicates, so the String “aaaaaa” will produce 720 permutations, which often isn’t 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.番石榴

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

<dependency>
<artifactId>guava</artifactId>
<version>31.0.1-jre</version>
</dependency>

Guava allows creating permutations with Collections2. The API is straightforward to use:

Guava允许用Collections2来创建排列组合。该API的使用非常简单明了。

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.

Collections2.permutations的结果是一个PermutationCollection，允许轻松访问permutations。所有的排列组合都是懒惰地创建的。

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.

TreatDuplicatesAs允许我们定义我们希望如何处理重复的内容。

## 7.结语

There’re 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 urge 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.

As always, the source code for the examples is available over on GitHub.