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

Java でのセットのパワーセット計算

コンピューター サイエンスでは、セットのパワーセットは、そのセットのすべての可能なサブセットのコレクションを表します。この記事では、最適な時間計算量を目指して、Java で整数セットのパワーセットを構築する方法について説明します。

問題ステートメント

Java で定義された整数セットが与えられた場合、私たちの目標は、パワーセットを計算する関数 getPowerset を作成することです。この関数の時間計算量を可能な限り最高にすることを目指しています。

解決策

パワーセットを計算する時間計算量は確かに O(2^n) です。ここで、nオリジナルセットのサイズです。以下の関数は、ジェネリクスとセットを利用してパワーセットの計算を効率的に実装します。

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    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;
}

Test

次のコードは、例を使用して関数を示しています。 input:

Set<Integer> mySet = new HashSet<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : SetUtils.powerSet(mySet)) {
    System.out.println(s);
}

Output

質問に示されているテストの出力には、{1, 2, 3}:

[]
[2]
[3]
[2, 3]
[1]
[1, 2]
[1, 3]
[1, 2, 3]

ジェネリックスと再帰を使用して getPowerset 関数を実装することにより、次の最適な時間計算量を実現します。 O(2^n) であり、Java でセットのパワーセットを計算するための効率的なソリューションです。

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