ホームページ > Java > &#&チュートリアル > Java でセットのパワーセットを効率的に計算するにはどうすればよいですか?

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

Patricia Arquette
リリース: 2024-11-30 04:21:15
オリジナル
261 人が閲覧しました

How to Efficiently Compute the Powerset of a Set in 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 サイトの他の関連記事を参照してください。

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート