Permutations of a String in Java – Java中字符串的排列组合

1. Introduction

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.

在本教程中，我们将学习如何使用第三方库轻松创建Java中的互变。更具体地说，我们将在一个字符串中处理互变。

2. Permutations

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”.

有时我们需要检查一个字符串值的所有可能的排列组合。通常是为了进行令人费解的在线编码练习，而在日常工作任务中则不太常见。例如，一个字符串 “abc “会有六种不同的排列方式：”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.

几个定义明确的算法可以帮助我们为一个特定的String值创建所有可能的排列组合。例如，最著名的是Heap的算法。然而，它是相当复杂和非直观的。递归方法，在此基础上，使事情变得更糟。

3. Elegant Solution

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.

此外，在处理String值时，如果不小心，有可能通过创建太多的实例来淹没String池。

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:

我们将在下面的例子中使用一个Helper.toCharacterList方法。这个方法封装了将String转换为List的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:

另外，我们将使用一个辅助方法来将List of Characters转换为String。

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

4. Apache Commons

4.阿帕奇公社

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

首先，让我们把Maven依赖commons-collections4加入项目。

<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:

总的来说，Apache提供了一个简单的API。CollectionUtils急于创建排列组合，所以我们在处理长的String值时应该小心。

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:

同时，为了使它能以懒人的方式工作，我们应该使用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 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.

这个库没有处理重复，所以字符串“aaaaa “将产生720个排列组合，这通常是不可取的。而且，PermutationIterator没有一个方法来获取排列组合的数量。在这种情况下，我们应该根据输入的大小来分别计算。

5. Guava

5.番石榴

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

首先，让我们把Guava库的Maven依赖性添加到项目中。

<dependency>
    <groupId>com.google.guava</groupId>
    <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:

此外，该类提供了一个API，用于创建没有重复的排列组合：。

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.

然而，这些方法的问题是，它们被注解了@Beta注解，这并不能保证这个API在未来的版本中不会发生变化。

6. CombinatoricsLib

6.组合学库（CombinatoricsLib

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

为了在项目中使用它，让我们添加combinatoricslib3 Maven依赖。

<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:

虽然这是一个小库，但它提供了许多组合学工具，包括排列组合。API本身是非常直观的，并且利用了Java流。让我们从一个特定的字符串或一个List字符中创建排列组合。

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.

上面的代码创建了一个生成器，将为String提供排列组合。排列组合将被懒散地检索。因此，我们只创建了一个生成器，并计算了预期的排列组合的数量。

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.

同时，通过这个库，我们可以识别重复的策略。如果我们用一个字符串 “aaaaa “作为例子，我们将只得到一个而不是720个相同的排列组合。

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. Conclusion

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.

像往常一样，这些例子的源代码可以在GitHub上找到。