Javaでの組み合わせの生成

1. 前書き

このチュートリアルでは、* Javaでのhttps://en.wikipedia.org/wiki/Combination[k-combinations]問題の解決方法について説明します*。
最初に、特定のサイズのすべての組み合わせを生成するために、再帰アルゴリズムと反復アルゴリズムの両方について説明し、実装します。 次に、一般的なJavaライブラリを使用してソリューションを確認します。

2. 組み合わせの概要

簡単に言えば、*組み合わせとは、特定のセット*の要素のサブセットです。
順列とは異なり、個々の要素を選択する順序は重要ではありません。 代わりに、特定の要素が選択範囲にあるかどうかのみを考慮します。
たとえば、カードゲームでは、52枚のカードで構成されるパックから5枚のカードを配る必要があります。 5枚のカードが選択された順番には興味がありません。 むしろ、どのカードが手にあるかだけを気にします。
問題によっては、考えられるすべての組み合わせを評価する必要があります。 これを行うために、さまざまな組み合わせを列挙します。
*一連の「n」要素から「r」要素を選択するさまざまな方法は、次の式で数学的に表現できます。*
link:/uploads/combination1-100x36.png%20100w []
したがって、最悪の場合、要素を選択する方法の数は指数関数的に増加する可能性があります。 したがって、大規模な母集団の場合、さまざまな選択を列挙することはできません。
そのような場合、いくつかの代表的な選択をランダムに選択する場合があります。 このプロセスは_sampling_と呼ばれます。
次に、さまざまなアルゴリズムを確認して組み合わせをリストします。

3. 組み合わせを生成する再帰的アルゴリズム

link:/java-recursion [再帰アルゴリズム]は通常、問題を同様の小さな問題に分割することで機能します。 このプロセスは、終了条件に到達するまで続きます。終了条件は基本条件でもあります。 次に、基本ケースを直接解決します。
*セットから要素を選択するタスクを細分化する2つの方法について説明します。*最初のアプローチでは、セット内の要素に関して問題を分割します。 2番目のアプローチでは、選択した要素のみを追跡することで問題を分割します。

3.1. セット全体の要素によるパーティション化

アイテムを1つずつ検査して、「_ n」アイテムから「_r」要素を選択するタスクを分けましょう。 セット内の各アイテムについて、選択に含めるか除外することができます。
*最初のアイテムを含める場合は、残りの「_n」「1」アイテムから「r」「1」要素を選択する必要があります*。 一方、*最初のアイテムを破棄する場合は、残りの「_n」「1」アイテムから「_r」要素を選択する必要があります。*
これは数学的に次のように表現できます。
link:/uploads/Selection_406.png []
次に、このアプローチの再帰的な実装を見てみましょう。
private void helper(List<int[]> 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);
    }
}
  • _helper_メソッドは、それ自体に対して2つの再帰呼び出しを行います。 最初の呼び出しには、現在の要素が含まれます。 2番目の呼び出しは、現在の要素を破棄します。*

    次に、この_helper_メソッドを使用して組み合わせジェネレーターを作成しましょう。
public List<int[]> generate(int n, int r) {
    List<int[]> combinations = new ArrayList<>();
    helper(combinations, new int[r], 0, n-1, 0);
    return combinations;
}
上記のコードでは、_generate_メソッドが_helper_メソッドの最初の呼び出しを設定し、適切なパラメーターを渡します。
次に、このメソッドを呼び出して組み合わせを生成しましょう。
List<int[]> 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<int[]> selection = generator.generate(N, R);
    assertEquals(nCr, selection.size());
}
必要なスタックサイズは、セット内の要素の数であることが簡単にわかります。 *セット内の要素の数が多い場合、たとえば最大呼び出しスタックの深さよりも大きい場合、スタックをオーバーフローさせて_StackOverflowError_を取得します*。
したがって、入力セットが大きい場合、このアプローチは機能しません。

3.2。 組み合わせの要素による分割

入力セットの要素を追跡する代わりに、*選択範囲の項目を追跡することでタスクを分割します*。
最初に、インデックス「1」から「_n」にインデックスを使用して、入力セットのアイテムを並べましょう。 これで、最初の「_n-r 1」項目から最初の項目を選択できます。
__kth __itemを選択したと仮定しましょう。 次に、残りの「_n」「k」の項目から「_r」「1」の項目を選択する必要があります。これは、「_ k 1」から「_n」に索引付けされています。
このプロセスを数学的に次のように表現します。
link:/uploads/combination3-100x7.png%20100w []
次に、*このアプローチを実装するための再帰的メソッドを書きましょう:*
private void helper(List<int[]> 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()_メソッドを再帰的に呼び出して残りの項目を選択します*。 必要な数のアイテムが選択されたら停止します。
次に、_helper_メソッドを使用して選択範囲を生成します。
public List<int[]> generate(int n, int r) {
    List<int[]> 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<int[]> selection = generator.generate(N, R);
    assertEquals(nCr, selection.size());
}
このアプローチで使用される呼び出しスタックのサイズは、選択範囲内の要素の数と同じです。 したがって、*このアプローチは、選択する要素の数が最大呼び出しスタック深度よりも少ない限り、大きな入力に対して機能します。*
選択する要素の数も多い場合、この方法は機能しません。

4. 反復アルゴリズム

反復アプローチでは、最初の組み合わせから始めます。 その後、*すべての組み合わせを生成するまで*、現在の組み合わせから次の組み合わせを生成し続けます*。
辞書の順序で組み合わせを生成しましょう。 最も低い辞書編集の組み合わせから始めます。
現在の組み合わせから次の組み合わせを取得するために、現在の組み合わせの中で右に増分できる場所を見つけます。 次に、場所をインクリメントし、その場所の右側に可能な限り低い辞書編集の組み合わせを生成します。
このアプローチに従うコードを書きましょう。
public List<int[]> generate(int n, int r) {
    List<int[]> 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;
}
次に、テストケースを記述しましょう。
@Test
public void givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount() {
    IterativeCombinationGenerator generator = new IterativeCombinationGenerator();
    List<int[]> selection = generator.generate(N, R);
    assertEquals(nCr, selection.size());
}
ここで、いくつかのJavaライブラリを使用して問題を解決しましょう。

5. 組み合わせを実装するJavaライブラリ

可能な限り、既存のライブラリ実装を展開するのではなく、再利用する必要があります。 このセクションでは、組み合わせを実装する次のJavaライブラリについて説明します。
  • Apache Commons

  • グアバ

  • CombinatoricsLib

5.1. Apache Commons

Apache Commonsの_https://commons.apache.org/proper/commons-math/javadocs/api-3.6/org/apache/commons/math3/util/CombinatoricsUtils.html [CombinatoricsUtils] _クラスは、多くの組み合わせユーティリティ関数を提供します。 特に、https://commons.apache.org/proper/commons-math/javadocs/api-3.6/org/apache/commons/math3/util/CombinatoricsUtils.html#combinationsIterator(int、%20int)[_combinationsIterator_]メソッドは、辞書式順序で組み合わせを生成するイテレータを返します。
最初に、Maven依存関係_https://search.maven.org/search?q = a:commons-math3 [commons-math3] _をプロジェクトに追加しましょう。
<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.6.1</version>
</dependency>
次に、* _ combinationsIterator_メソッドを使用して組み合わせを出力しましょう*:
public static void generate(int n, int r) {
    Iterator<int[]> iterator = CombinatoricsUtils.combinationsIterator(n, r);
    while (iterator.hasNext()) {
        final int[] combination = iterator.next();
        System.out.println(Arrays.toString(combination));
    }
}

5.2. Google Guava

Guavaライブラリの_https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/Sets.html [Sets] _クラスは、セット関連の操作のためのユーティリティメソッドを提供します。 * _https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/Sets.html#combinations-java.util.Set-int- [combinations] _メソッドが返す指定されたサイズ*のすべてのサブセット。
まず、https://search.maven.org/search?q = g:com.google.guava%20a:guava [Guava library]のMaven依存関係をプロジェクトに追加しましょう。
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>27.0.1-jre</version>
</dependency>
次に、* _ combinations_メソッドを使用して組み合わせを生成しましょう*:
Set<Set<Integer>> combinations = Sets.combinations(ImmutableSet.of(0, 1, 2, 3, 4, 5), 3);
ここでは、_ImmutableSet.of_メソッドを使用して、指定された番号からセットを作成しています。

5.3. CombinatoricsLib

  • https://github.com/dpaukov/combinatoricslib3 [CombinatoricsLib]は、順列、組み合わせ、サブセット、整数パーティション、デカルト積用の小さくてシンプルなJavaライブラリです。*

    プロジェクトで使用するには、_https://search.maven.org/search?q = g:com.github.dpaukov%20AND%20a:combinatoricslib3 [combinatoricslib3] _ Maven依存関係を追加しましょう。
<dependency>
    <groupId>com.github.dpaukov</groupId>
    <artifactId>combinatoricslib3</artifactId>
    <version>3.3.0</version>
</dependency>
次に、*ライブラリを使用して組み合わせを印刷しましょう:*
Generator.combination(0, 1, 2, 3, 4, 5)
  .simple(3)
  .stream()
  .forEach(System.out::println);
これにより、実行時に次の出力が生成されます。
[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]
その他の例は、_https://github.com/dpaukov/combinatoricslib3-example [combinatoricslib3-example] _で入手できます。

6. 結論

この記事では、いくつかのアルゴリズムを実装して組み合わせを生成しました。
また、いくつかのライブラリの実装も確認しました。 通常、独自のロールを使用する代わりにこれらを使用します。
いつものように、完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/java-math[GitHubで]にあります。