자바에서 조합 생성

1. 소개

이 튜토리얼에서는 Java의 k-combinations 문제 해결 방법에 대해 설명합니다 .

먼저 주어진 크기의 모든 조합을 생성하기 위해 재귀 및 반복 알고리즘을 모두 논의하고 구현합니다. 그런 다음 공통 Java 라이브러리를 사용하여 솔루션을 검토합니다.

2. 조합 개요

간단히 말해서 조합은 주어진 세트의 요소의 하위 집합입니다 .

순열과 달리 개별 요소를 선택하는 순서는 중요하지 않습니다. 대신 특정 요소가 선택 항목에 있는지 여부 만 고려합니다.

예를 들어, 카드 게임에서 52 장의 카드로 구성된 팩에서 5 장의 카드를 처리해야합니다. 우리는 5 개의 카드가 선택된 순서에 관심이 없습니다. 오히려 우리는 손에 어떤 카드가 있는지 만 신경을 씁니다.

일부 문제는 가능한 모든 조합을 평가해야합니다. 이를 위해 다양한 조합을 열거합니다.

"n"요소 집합에서 "r"요소를 선택하는 고유 한 방법의 수는 다음 공식을 사용하여 수학적으로 표현할 수 있습니다.

따라서 요소를 선택하는 방법의 수는 최악의 경우 기하 급수적으로 증가 할 수 있습니다. 따라서 대규모 인구의 경우 다른 선택을 열거하는 것이 불가능할 수 있습니다.

그러한 경우, 우리는 몇 가지 대표적인 선택을 무작위로 선택할 수 있습니다. 이 과정을 샘플링 이라고 합니다.

다음으로 다양한 알고리즘을 검토하여 조합을 나열합니다.

3. 조합을 생성하는 재귀 알고리즘

재귀 알고리즘은 일반적으로 문제를 유사한 작은 문제로 분할하여 작동합니다. 이 프로세스는 기본 케이스이기도 한 종료 조건에 도달 할 때까지 계속됩니다. 그런 다음 기본 케이스를 직접 해결합니다.

집합에서 요소를 선택하는 작업을 세분화하는 두 가지 방법에 대해 설명합니다. 첫 번째 방법은 세트의 요소 측면에서 문제를 나눕니다. 두 번째 방법은 선택한 요소 만 추적하여 문제를 나눕니다.

3.1. 전체 세트의 요소로 분할

항목을 하나씩 검사하여 “ n” 항목 에서“ r” 요소를 선택하는 작업을 나눕니다 . 세트의 각 항목에 대해 선택 항목에 포함하거나 제외 할 수 있습니다.

첫 번째 항목을 포함하는 경우 나머지 " n – 1" 항목 에서 "r – 1" 요소 를 선택해야 합니다 . 반면에 첫 번째 항목을 버리면 나머지 " n – 1" 항목 중에서 " r" 요소 를 선택해야 합니다.

이것은 수학적으로 다음과 같이 표현 될 수 있습니다.

이제이 접근 방식의 재귀 적 구현을 ​​살펴 보겠습니다.

private void helper(List combinations, int data[], int start, int end, int index) { if (index == data.length) { int[] combination = data.clone(); combinations.add(combination); } else if (start <= end) { data[index] = start; helper(combinations, data, start + 1, end, index + 1); helper(combinations, data, start + 1, end, index); } }

도우미 방법은 자체 두 개의 재귀 호출합니다. 첫 번째 호출에는 현재 요소가 포함됩니다. 두 번째 호출은 현재 요소를 버립니다.

다음으로이 도우미 메서드를 사용하여 조합 생성기를 작성해 보겠습니다 .

public List generate(int n, int r) { List combinations = new ArrayList(); helper(combinations, new int[r], 0, n-1, 0); return combinations; }

위 코드에서 generate 메서드는 도우미 메서드에 대한 첫 번째 호출을 설정 하고 적절한 매개 변수를 전달합니다.

다음으로이 메서드를 호출하여 조합을 생성 해 보겠습니다.

List combinations = generate(N, R); for (int[] combination : combinations) { System.out.println(Arrays.toString(combination)); } System.out.printf("generated %d combinations of %d items from %d ", combinations.size(), R, N);

프로그램을 실행하면 다음과 같은 출력이 표시됩니다.

[0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] generated 10 combinations of 2 items from 5

마지막으로 테스트 케이스를 작성해 보겠습니다.

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount() { SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

필요한 스택 크기가 세트의 요소 수라는 것을 쉽게 알 수 있습니다. 집합의 요소 수가 최대 호출 스택 깊이보다 크면 스택이 오버플로되고 StackOverflowError가 발생 합니다.

따라서이 접근 방식은 입력 집합이 큰 경우에는 작동하지 않습니다.

3.2. 조합의 요소로 분할

입력 집합의 요소를 추적하는 대신 선택 항목의 항목을 추적하여 작업을 나눕니다 .

먼저 "1"~ " n" 인덱스를 사용하여 입력 집합의 항목을 정렬 해 보겠습니다 . 이제 첫 번째 " n-r + 1" 항목 에서 첫 번째 항목을 선택할 수 있습니다 .

k 번째 항목 을 선택했다고 가정 해 보겠습니다 . 그런 다음 " k + 1" 에서 " n"으로 인덱싱 된 나머지 " n – k" 항목 에서 " r – 1" 항목 을 선택해야합니다 .

우리는이 과정을 다음과 같이 수학적으로 표현합니다.

다음 으로이 접근 방식을 구현하는 재귀 메서드를 작성해 보겠습니다.

private void helper(List combinations, int data[], int start, int end, int index) { if (index == data.length) { int[] combination = data.clone(); combinations.add(combination); } else { int max = Math.min(end, end + 1 - data.length + index); for (int i = start; i <= max; i++) { data[index] = i; helper(combinations, data, i + 1, end, index + 1); } } }

위의 코드에서 for 루프는 다음 항목 을 선택하고 나머지 항목을 선택하기 위해 helper () 메서드를 재귀 적으로 호출합니다 . 필요한 수의 항목이 선택되면 중지됩니다.

다음으로 도우미 메서드를 사용하여 선택을 생성 해 보겠습니다 .

public List generate(int n, int r) { List combinations = new ArrayList(); helper(combinations, new int[r], 0, n - 1, 0); return combinations; }

마지막으로 테스트 케이스를 작성해 보겠습니다.

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExpectedCount() { SelectionRecursiveCombinationGenerator generator = new SelectionRecursiveCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

이 접근 방식에서 사용되는 호출 스택 크기는 선택 항목의 요소 수와 동일합니다. 따라서이 접근 방식은 선택할 요소 수가 최대 호출 스택 깊이보다 적 으면 큰 입력에 대해 작동 할 수 있습니다.

선택할 요소의 수도 많으면이 방법이 작동하지 않습니다.

4. 반복 알고리즘

반복적 접근 방식에서는 초기 조합으로 시작합니다. 그런 다음 모든 조합을 생성 할 때까지 현재 조합에서 다음 조합을 계속 생성합니다 .

사전 순으로 조합을 생성 해 봅시다. 가장 낮은 사전 조합부터 시작합니다.

In order to get the next combination from the current one, we find the rightmost location in the current combination that can be incremented. Then, we increment the location and generate the lowest possible lexicographic combination to the right of that location.

Let's write the code which follows this approach:

public List generate(int n, int r) { List combinations = new ArrayList(); int[] combination = new int[r]; // initialize with lowest lexicographic combination for (int i = 0; i < r; i++) { combination[i] = i; } while (combination[r - 1] < n) { combinations.add(combination.clone()); // generate next combination in lexicographic order int t = r - 1; while (t != 0 && combination[t] == n - r + t) { t--; } combination[t]++; for (int i = t + 1; i < r; i++) { combination[i] = combination[i - 1] + 1; } } return combinations; }

Next, let's write the test case:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount() { IterativeCombinationGenerator generator = new IterativeCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

Now, let us use some Java libraries to solve the problem.

5. Java Libraries Implementing Combinations

As far as possible, we should reuse existing library implementations instead of rolling out our own. In this section, we'll explore the following Java libraries that implement combinations:

  • Apache Commons
  • Guava
  • CombinatoricsLib

5.1. Apache Commons

The CombinatoricsUtils class from Apache Commons provides many combination utility functions. In particular, the combinationsIterator method returns an iterator that will generate combinations in lexicographic order.

First, let's add the Maven dependency commons-math3 to the project:

 org.apache.commons commons-math3 3.6.1 

Next, let's use the combinationsIterator method to print the combinations:

public static void generate(int n, int r) { Iterator iterator = CombinatoricsUtils.combinationsIterator(n, r); while (iterator.hasNext()) { final int[] combination = iterator.next(); System.out.println(Arrays.toString(combination)); } }

5.2. Google Guava

The Sets class from Guava library provides utility methods for set-related operations. The combinations method returns all subsets of a given size.

First, let's add the maven dependency for the Guava library to the project:

 com.google.guava guava 27.0.1-jre 

Next, let's use the combinations method to generate combinations:

Set
    
      combinations = Sets.combinations(ImmutableSet.of(0, 1, 2, 3, 4, 5), 3);
    

Here, we are using the ImmutableSet.of method to create a set from the given numbers.

5.3. CombinatoricsLib

CombinatoricsLib is a small and simple Java library for permutations, combinations, subsets, integer partitions, and cartesian product.

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

 com.github.dpaukov combinatoricslib3 3.3.0 

Next, let's use the library to print the combinations:

Generator.combination(0, 1, 2, 3, 4, 5) .simple(3) .stream() .forEach(System.out::println);

This produces the following output on execution:

[0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 1, 5] [0, 2, 3] [0, 2, 4] [0, 2, 5] [0, 3, 4] [0, 3, 5] [0, 4, 5] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5]

More examples are available at combinatoricslib3-example.

6. Conclusion

In this article, we implemented a few algorithms to generate combinations.

또한 몇 가지 라이브러리 구현을 검토했습니다. 일반적으로 우리는 우리 자신의 롤링 대신 이것을 사용합니다.

평소처럼 전체 소스 코드는 GitHub에서 찾을 수 있습니다.