Java でセットのパワーセットを効率的に生成するにはどうすればよいですか?

Java でのパワーセットの検索: 効率的なアプローチ

セットのパワーセットには、元のセットの考えられるすべてのサブセットが含まれます。サイズ n のセットの場合、パワーセットには 2^n 個の要素が含まれます。 Java では、効率的なアルゴリズムを使用してパワーセットの作成を処理するのが一般的です。

次の例を考えてみましょう。

Set mySet = new HashSet<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set> ; powerSet = getPowerset(mySet);

この設定のタスクは、最適な時間計算量で mySet のパワーセットを生成する getPowerset 関数を設計することです。

最適な時間計算量: O (2^n)

前述したように、パワーセットには 2^n 要素が含まれています。したがって、これらすべての要素を生成するには、本質的に O(2^n) の時間計算量が必要になります。

実装

次のコードは、汎用的で効率的な実装を提供します。

パブリック静的設定<設定> powerSet(SetoriginalSet) {

Set<Set<T>> sets = new HashSet<>();
if (originalSet.isEmpty()) {
    sets.add(new HashSet<>());
    return sets;
}
List<T> list = new ArrayList<>(originalSet);
T head = list.get(0);
Set<T> rest = new HashSet<>(list.subList(1, list.size()));
for (Set<T> set : powerSet(rest)) {
    Set<T> newSet = new HashSet<>();
    newSet.add(head);
    newSet.addAll(set);
    sets.add(newSet);
    sets.add(set);
}
return sets;

}

例

前に示した例を利用します:

を設定します。 mySet = new HashSet<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set s : パワーセット(mySet)) {

System.out.println(s);

}

出力は次のようになります:

{}
{1}
{2}
{1, 2}
{3}
{1, 3}
{2, 3}
{1, 2, 3}

これは、時間計算量が O(2^n) である指定されたセットのパワーセットの作成を示します。

以上がJava でセットのパワーセットを効率的に生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。