1. 소개
순열 은 집합의 요소를 재배열하는 것입니다 . 즉, 수집 순서의 모든 가능한 변형입니다.
이 사용방법(예제)에서는 타사 라이브러리를 사용하여 Java에서 순열을 쉽게 만드는 방법을 배웁니다 . 더 구체적으로, 우리는 문자열에서 순열 작업을 할 것입니다.
2. 순열
때로는 문자열 값의 가능한 모든 순열을 확인해야 합니다. 종종 마음이 흔들리는 온라인 코딩 연습에 사용되며 일상적인 작업에는 덜 자주 사용됩니다. 예를 들어 문자열 "abc"는 "abc", "acb", "cab", "bac", "bca", "cba"의 6가지 다른 방법으로 문자를 정렬할 수 있습니다.
몇 가지 잘 정의된 알고리즘은 특정 문자열 값 에 대해 가능한 모든 순열을 만드는 데 도움이 될 수 있습니다 . 예를 들어 가장 유명한 것은 힙 알고리즘입니다. 그러나 매우 복잡하고 직관적이지 않습니다. 재귀적 접근 방식은 문제를 더욱 악화시킵니다.
3. 우아한 솔루션
순열을 생성하는 알고리즘을 구현하려면 사용자 지정 논리를 작성해야 합니다. 구현에서 실수하기 쉽고 시간이 지남에 따라 올바르게 작동하는지 테스트하기가 어렵습니다. 또한 이전에 작성한 것을 다시 작성하는 것은 의미가 없습니다.
또한 문자열 값으로 작업 할 때 신중하게 수행하지 않으면 너무 많은 인스턴스를 생성 하여 문자열 풀 을 넘칠 수 있습니다.
현재 이러한 기능을 제공하는 라이브러리는 다음과 같습니다.
- 아파치 커먼즈
- 구아바
- CombinatoricsLib
이 라이브러리를 사용하여 String 값에 대한 모든 순열을 찾아봅시다. 이러한 라이브러리가 순열에 대한 지연 트래버스를 허용하고 입력 값에서 중복을 처리하는 방법에 주의를 기울일 것 입니다.
아래 예제에서는 Helper.toCharacterList 메서드를 사용 합니다. 이 메서드는 문자열 을 문자 List 으로 변환하는 복잡성을 캡슐화합니다 .
static List<Character> toCharacterList(final String string) {
return string.chars().mapToObj(s -> ((char) s)).collect(Collectors.toList());
}또한 도우미 메서드를 사용하여 문자 List 을 문자열 로 변환할 것입니다 .
static String toString(Collection<Character> collection) {
return collection.stream().map(s -> s.toString()).collect(Collectors.joining());
}4. 아파치 커먼즈
먼저 Maven 의존성 commons-collections4 를 프로젝트에 추가해 보겠습니다.
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-collections4</artifactId>
<version>4.4</version>
</dependency>전반적으로 Apache는 간단한 API를 제공합니다. CollectionUtils 는 열심히 순열을 생성하므로 긴 문자열 값 으로 작업할 때 주의해야 합니다 .
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());
}동시에 Lazy 접근 방식으로 작동하게 하려면 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;
}이 라이브러리는 중복을 처리하지 않으므로 문자열 "aaaaaa"는 종종 바람직하지 않은 720개의 순열을 생성합니다. 또한 PermutationIterator 에는 순열 수를 가져오는 메서드가 없습니다. 이 경우 입력 크기에 따라 별도로 계산해야 합니다.
5. 구아바
먼저 Guava 라이브러리 에 대한 Maven 의존성을 프로젝트에 추가해 보겠습니다.
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-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. CombinatoricsLib
프로젝트에서 사용하려면 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에서 사용할 수 있습니다 .
