Java中字符串的排列
一、簡介
排列是集合中元素的重新排列。換句話說，它是收集順序的所有可能變化。
在本教程中，我們將學習如何使用第三方庫在 Java 中輕鬆創建排列。更具體地說，我們將處理字符串中的排列。
2.排列
有時我們需要檢查字符串值的所有可能排列。通常用於令人難以置信的在線編碼練習，而不是用於日常工作任務。例如，字符串“abc”將有六種不同的方式來排列其中的字符：“abc”、“acb”、“cab”、“bac”、“bca”、“cba”。
一些定義明確的算法可以幫助我們為特定的String值創建所有可能的排列。比如最著名的就是Heap的算法。但是，它非常複雜且不直觀。最重要的是，遞歸方法使事情變得更糟。
3.優雅的解決方案
實現生成排列的算法將需要編寫自定義邏輯。在實現中很容易出錯，並且很難測試它是否隨著時間的推移正常工作。而且，重寫之前寫的東西也沒有任何意義。
此外，在使用String值時，如果不小心創建太多實例，可能會導致String池氾濫。
以下是目前提供此類功能的庫：
- 阿帕奇公地
- 番石榴
- 組合學庫
讓我們嘗試使用這些庫查找字符串值的所有排列。我們將**關注這些庫是否允許對排列進行延遲遍歷以及它們如何處理輸入值中的重複項。**
我們將在下面的示例中使用Helper.toCharacterList方法。此方法封裝了將String轉換為List of Characters的複雜性：
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. 結論
特別是有很多方法可以處理組合和排列。所有這些庫都可以在這方面提供很大幫助。值得嘗試所有這些並決定哪一個適合您的需求。儘管許多人有時會敦促編寫所有代碼，但將時間浪費在已經存在並提供良好功能的東西上是沒有意義的。
與往常一樣，示例的源代碼可在 GitHub 上獲得。