1. 序章

このチュートリアルでは、Javaのk-combinations問題の解決策について説明します。

最初に、特定のサイズのすべての組み合わせを生成するための再帰的アルゴリズムと反復的アルゴリズムの両方について説明し、実装します。 次に、一般的なJavaライブラリを使用してソリューションを確認します。

2. 組み合わせの概要

簡単に言えば、組み合わせは、特定のセットの要素のサブセットです。

順列とは異なり、個々の要素を選択する順序は重要ではありません。 代わりに、特定の要素が選択に含まれているかどうかのみを考慮します。

たとえば、カードゲームでは、52枚のカードからなるパックから5枚のカードを配る必要があります。 5枚のカードが選ばれた順番には興味がありません。 むしろ、どのカードが手にあるかだけを気にします。

一部の問題では、考えられるすべての組み合わせを評価する必要があります。 これを行うために、さまざまな組み合わせを列挙します。

「n」要素のセットから「r」要素を選択するための明確な方法の数は、次の式で数学的に表すことができます。

したがって、要素を選択する方法の数は、最悪の場合、指数関数的に増加する可能性があります。 したがって、人口が多い場合は、さまざまな選択肢を列挙できない場合があります。

そのような場合、いくつかの代表的な選択肢をランダムに選択することがあります。 このプロセスはサンプリングと呼ばれます。

次に、さまざまなアルゴリズムを確認して、組み合わせを一覧表示します。

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

再帰的アルゴリズムは通常、問題を同様の小さな問題に分割することによって機能します。 このプロセスは、基本ケースでもある終了条件に到達するまで続きます。 次に、基本ケースを直接解決します。

セットから要素を選択するタスクを細分化する2つの方法について説明します。最初のアプローチは、セット内の要素の観点から問題を分割します。 2番目のアプローチは、選択した要素のみを追跡することによって問題を分割します。

3.1. セット全体の要素による分割

n」アイテムから「r」要素を選択するタスクを、アイテムを1つずつ調べて分割してみましょう。 セット内の各アイテムについて、選択に含めることも除外することもできます。

最初のアイテムを含める場合は、残りの「n –1」アイテムから「r–1」要素を選択する必要があります。 一方、最初のアイテムを破棄する場合は、残りの「n –1」アイテムから「r」要素を選択する必要があります。

これは数学的に次のように表すことができます。

それでは、このアプローチの再帰的な実装を見てみましょう。

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アイテムを選択したと仮定します。 次に、「 k + 1」から「」のインデックスが付けられた残りの「n–k」アイテムから「 r–1」アイテムを選択する必要があります。 n”

このプロセスを数学的に次のように表現します。

次に、このアプローチを実装するための再帰メソッドを記述しましょう:

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

ApacheCommonsのCombinatoricsUtilsクラスは、多くの組み合わせユーティリティ関数を提供します。 特に、 combinationsIterator メソッドは、辞書式順序で組み合わせを生成するイテレーターを返します。

まず、Mavenの依存関係commons-math3をプロジェクトに追加しましょう。

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.6.1</version>
</dependency>

次に、combinationsIteratorメソッドを使用してcombinationsを出力しましょう。

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ライブラリのSetsクラスは、セット関連の操作のためのユーティリティメソッドを提供します。 combinationsメソッドは指定されたサイズのすべてのサブセットを返します

まず、GuavaライブラリのMaven依存関係をプロジェクトに追加しましょう。

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

次に、組み合わせメソッドを使用して組み合わせを生成しましょう

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

ここでは、 ImmutableSet.of メソッドを使用して、指定された番号からセットを作成しています。

5.3. CombinatoricsLib

CombinatoricsLib は、順列、組み合わせ、サブセット、整数パーティション、およびデカルト積のための小さくて単純なJavaライブラリです。

プロジェクトで使用するには、 combinatoricslib3Maven依存関係を追加しましょう。

<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]

その他の例は、combinatoricslib3-exampleで入手できます。

6. 結論

この記事では、組み合わせを生成するためにいくつかのアルゴリズムを実装しました。

また、いくつかのライブラリの実装を確認しました。 通常、独自にロールする代わりにこれらを使用します。

いつものように、完全なソースコードはGitHubにあります。