一、简介
排列是集合中元素的重新排列。换句话说，它是收集顺序的所有可能变化。
在本教程中，我们将学习如何使用第三方库在Java 中轻松创建排列。更具体地说，我们将处理字符串中的排列。
2.排列
有时我们需要检查字符串值的所有可能排列。通常用于令人难以置信的在线编码练习，而不是用于日常工作任务。例如，字符串“abc”将有六种不同的方式来排列其中的字符：“abc”、“acb”、“cab”、“bac”、“bca”、“cba”。
一些定义明确的算法可以帮助我们为特定的String值创建所有可能的排列。比如最著名的就是Heap的算法。但是，它非常复杂且不直观。最重要的是，递归方法使事情变得更糟。
3.优雅的解决方案
实现生成排列的算法将需要编写自定义逻辑。在实现中很容易出错，并且很难测试它是否随着时间的推移正常工作。而且，重写之前写的东西也没有任何意义。
此外，在使用String值时，如果不小心创建太多实例，可能会导致String池泛滥。
以下是目前提供此类功能的库：
阿帕奇公地
番石榴
组合学库
让我们尝试使用这些库查找字符串值的所有排列。我们将**关注这些库是否允许对排列进行延迟遍历以及它们如何处理输入值中的重复项。**
我们将在下面的示例中使用Helper.toCharacterList方法。此方法封装了将String转换为ListofCharacters的复杂性：
static List<Character> toCharacterList(final String string) {
return string.chars().mapToObj(s -> ((char) s)).collect(Collectors.toList());
}
此外，我们将使用辅助方法将Characters List转换为String：
static String toString(Collection<Character> collection) {
return collection.stream().map(s -> s.toString()).collect(Collectors.joining());
}
4. Apache Commons
首先，让我们在项目中添加Maven 依赖[commons-collections4](https://search.maven.org/search?q=g:org.apache.commons%20AND%20a:commons-collections4)：
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-collections4</artifactId>
<version>4.4</version>
</dependency>
总的来说，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());
}
同时，为了让它使用惰性方法，我们应该使用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;
}
该库不处理重复项，因此String“aaaaaa”将产生720 个排列，这通常是不可取的。此外，PermutationIterator没有获取排列数量的方法。在这种情况下，我们应该根据输入大小分别计算它们。
5.番石榴
首先，让我们将Guava 库的Maven 依赖添加到项目中：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version><span class="hljs-number">31.0</span><span class="hljs-number">.1</span>-jre</version>
</dependency>
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());
}
Collections2.permutations的结果是一个PermutationCollection，它允许轻松访问排列。所有排列都是惰性创建的。
此外，这个类提供了一个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());
}
但是，这些方法的问题在于它们使用@Beta注释进行了注释，这不能保证此API 在未来的版本中不会更改。
6. 组合学库
要在项目中使用它，让我们添加[combinatoricslib3](https://search.maven.org/search?q=g:com.github.dpaukov%20AND%20a:combinatoricslib3)Maven 依赖项：
<dependency>
<groupId>com.github.dpaukov</groupId>
<artifactId>combinatoricslib3</artifactId>
<version>3.3.3</version>
</dependency>
虽然这是一个小型库，但它提供了许多组合工具，包括排列。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());
}
上面的代码创建了一个生成器，它将为字符串提供排列。排列将被延迟检索。因此，我们只创建了一个生成器并计算了预期的排列数。
同时，通过这个库，我们可以识别重复的策略。如果我们以字符串“aaaaaa”为例，我们将只得到一个而不是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允许我们定义我们希望如何处理重复项。
7. 结论
特别是有很多方法可以处理组合和排列。所有这些库都可以在这方面提供很大帮助。值得尝试所有这些并决定哪一个适合您的需求。尽管许多人有时会敦促编写所有代码，但将时间浪费在已经存在并提供良好功能的东西上是没有意义的。
0 评论