Javaの組み合わせ問題の概要
1. 概要
このチュートリアルでは、いくつかの一般的な組み合わせの問題を解決する方法を学びます。 それらは、日常の仕事ではあまり役に立たない可能性があります。 ただし、アルゴリズムの観点からは興味深いものです。 テスト目的で便利な場合があります。
これらの問題を解決するには、さまざまなアプローチがあることに注意してください。 提示されたソリューションを理解しやすいものにするように努めました。
2. 順列の生成
まず、順列から始めましょう。 順列とは、順序が異なるようにシーケンスを再配置する行為です。
数学からわかるように、
n！ = 1 *2*…*n
したがって、たとえば、シーケンス [1、2、3] の場合、6つの順列があります。
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]階乗は非常に速く成長します— 10個の要素のシーケンスに対して、3,628,800の異なる順列があります！ この場合、すべての要素が異なるシーケンスの並べ替えについて説明します。
2.1. アルゴリズム
再帰的な方法で順列を生成することを検討することをお勧めします。
このような状態で行う唯一の作業は、要素を残りのすべての要素と交換し、変更されたシーケンスとインデックスが1つ増加した状態への遷移を実行することです。
例を挙げて説明しましょう。
[1、2、3、4]の4つの要素のシーケンスのすべての順列を生成します。 したがって、24の順列があります。 次の図は、アルゴリズムの部分的な手順を示しています。
ツリーの各ノードは状態として理解できます。上部の赤い数字は、現在処理されている要素のインデックスを示します。 ノードの緑色の数字はスワップを示しています。
したがって、インデックスがゼロに等しい状態 [1、2、3、4]から開始します。 最初の要素を各要素（何も交換しない最初の要素を含む）と交換し、次の状態に進みます。
これで、目的の順列が右側の最後の列に表示されます。
2.2. Javaの実装
Javaで書かれたアルゴリズムは短いです：
private static void permutationsInternal(List<Integer> sequence, List<List<Integer>> results, int index) {
if (index == sequence.size() - 1) {
permutations.add(new ArrayList<>(sequence));
}
for (int i = index; i < sequence.size(); i++) {
swap(sequence, i, index);
permutationsInternal(sequence, permutations, index + 1);
swap(sequence, i, index);
}
}この関数は、現在処理されているシーケンス、結果（順列）、および現在処理されている要素のインデックスの3つのパラメーターを取ります。
最初に行うことは、最後の要素に到達したかどうかを確認することです。 その場合、シーケンスを結果リストに追加します。
次に、forループでスワップを実行し、メソッドを再帰的に呼び出してから、要素をスワップバックします。
最後の部分はちょっとしたパフォーマンスのトリックです。再帰呼び出しごとに新しいシーケンスを作成しなくても、同じsequenceオブジェクトを常に操作できます。
また、ファサードメソッドの下で最初の再帰呼び出しを非表示にすることもお勧めします。
public static List<List<Integer>> generatePermutations(List<Integer> sequence) {
List<List<Integer>> permutations = new ArrayList<>();
permutationsInternal(sequence, permutations, 0);
return permutations;
}
3. セットのべき集合の生成
もう1つの一般的な問題は、セットのべき集合を生成することです。 定義から始めましょう：
セットSのべき集合（またはべき集合）は、空のセットとS自体を含むSのすべてのサブセットのセットです。
したがって、たとえば、セット [a、b、c] が与えられた場合、べき集合には8つのサブセットが含まれます。
[]
[a]
[b]
[c]
[a, b]
[a, c]
[b, c]
[a, b, c]数学から、 n 要素を含むセットの場合、べき集合には2^n個のサブセットが含まれている必要があることがわかります。 この数も急速に増加しますが、階乗ほど速くはありません。
3.1. アルゴリズム
今回は再帰的にも考えていきます。 これで、状態は2つのもので構成されます。セットで現在処理されている要素のインデックスとアキュムレータです。
現在の要素をアキュムレータに配置するかどうかという、各状態で2つの選択肢を使用して決定を行う必要があります。インデックスがセットの最後に到達すると、可能なサブセットが1つあります。 このようにして、可能なすべてのサブセットを生成できます。
3.2. Javaの実装
Javaで書かれたアルゴリズムはかなり読みやすいです：
private static void powersetInternal(
List<Character> set, List<List<Character>> powerset, List<Character> accumulator, int index) {
if (index == set.size()) {
results.add(new ArrayList<>(accumulator));
} else {
accumulator.add(set.get(index));
powerSetInternal(set, powerset, accumulator, index + 1);
accumulator.remove(accumulator.size() - 1);
powerSetInternal(set, powerset, accumulator, index + 1);
}
}この関数は、サブセットを生成するセット、結果のべき集合、アキュムレータ、および現在処理されている要素のインデックスの4つのパラメータを取ります。
簡単にするために、
さらに、単一の要素は単一の文字（Javaでは文字クラス）で表されます。
最初に、インデックスが設定サイズを超えているかどうかを確認します。超えている場合は、アキュムレータを結果セットに入れます。超えていない場合は、次のようにします。
- 現在考慮されている要素をアキュムレータに入れます
- インクリメントされたインデックスと拡張されたアキュムレータを使用して再帰呼び出しを行う
- 以前に追加したアキュムレータから最後の要素を削除します
- アキュムレータを変更せず、インデックスをインクリメントして、もう一度呼び出しを行います
ここでも、ファサードメソッドを使用して実装を非表示にします。
public static List<List<Character>> generatePowerset(List<Character> sequence) {
List<List<Character>> powerset = new ArrayList<>();
powerSetInternal(sequence, powerset, new ArrayList<>(), 0);
return powerset;
}4. 組み合わせの生成
さて、組み合わせに取り組む時が来ました。 これを次のように定義します。
k-セットの組み合わせSは、 S、とは異なる k のサブセットであり、アイテムの順序は重要ではありません。
k-combinations の数は、二項係数で表されます。
したがって、たとえば、セット [a、b、c] の場合、3つの2-組み合わせがあります。
[a, b]
[a, c]
[b, c]組み合わせには、多くの組み合わせの使用法と説明があります。 例として、16チームで構成されるサッカーリーグがあるとします。 いくつの異なる一致を見ることができますか？
答えは 、120と評価されます。
4.1. アルゴリズム
概念的には、パワーセットの以前のアルゴリズムと同様のことを行います。 現在処理されている要素のインデックスとアキュムレータで構成される状態を持つ再帰関数があります。
繰り返しますが、各状態について同じ決定があります。要素をアキュムレータに追加しますか？ ただし、今回は追加の制限があります。アキュムレータはk要素。を超えることはできません。
二項係数は必ずしも大きな数である必要はないことに注意してください。 例えば：
は4,950に等しいが、
30桁です！
4.2. Javaの実装
簡単にするために、セット内の要素は整数であると想定しています。
アルゴリズムのJava実装を見てみましょう。
private static void combinationsInternal(
List<Integer> inputSet, int k, List<List<Integer>> results, ArrayList<Integer> accumulator, int index) {
int needToAccumulate = k - accumulator.size();
int canAcculumate = inputSet.size() - index;
if (accumulator.size() == k) {
results.add(new ArrayList<>(accumulator));
} else if (needToAccumulate <= canAcculumate) {
combinationsInternal(inputSet, k, results, accumulator, index + 1);
accumulator.add(inputSet.get(index));
combinationsInternal(inputSet, k, results, accumulator, index + 1);
accumulator.remove(accumulator.size() - 1);
}
}今回の関数には、入力セット、 k パラメーター、結果リスト、アキュムレーター、および現在処理されている要素のインデックスの5つのパラメーターがあります。
ヘルパー変数を定義することから始めます。
- needToAccumulate –適切な組み合わせを取得するためにアキュムレータに追加する必要のある要素の数を示します
- canAcculumate –アキュムレータに追加できる要素の数を示します
ここで、アキュムレータのサイズがkに等しいかどうかを確認します。 もしそうなら、コピーした配列を結果リストに入れることができます。
別のケースでは、セットの残りの部分にまだ十分な要素がある場合、2つの別々の再帰呼び出しを行います。現在処理されている要素をアキュムレータに入れる場合と入れない場合です。この部分は、以前にパワーセットを生成しました。
もちろん、このメソッドは少し速く動作するように作成できたはずです。 たとえば、後でneedToAccumulate変数とcanAcculumate変数を宣言できます。 ただし、読みやすさに重点を置いています。
繰り返しますが、ファサードメソッドは実装を隠します：
public static List<List<Integer>> combinations(List<Integer> inputSet, int k) {
List<List<Integer>> results = new ArrayList<>();
combinationsInternal(inputSet, k, results, new ArrayList<>(), 0);
return results;
}5. 概要
この記事では、さまざまな組み合わせの問題について説明しました。 さらに、Javaの実装でそれらを解決するための簡単なアルゴリズムを示しました。 場合によっては、これらのアルゴリズムが異常なテストのニーズに役立つことがあります。
いつものように、テストを含む完全なソースコードは、GitHubでから入手できます。
