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

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

Linda Hamilton
リリース: 2024-12-14 22:41:14
オリジナル
252 人が閲覧しました

How to Efficiently Generate the Power Set of a Set in Java?

Java でのセットのパワーセットの生成

セットのパワーセットは、そのセットのすべてのサブセットのセットです。たとえば、{1, 2, 3} のパワーセットは次のとおりです:

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

セットがあるとします。 Java:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);
ログイン後にコピー

最適な時間計算量で getPowerset 関数を作成するにはどうすればよいですか?

解決策

powerset 関数の時間計算量は O(2^n) です。n はセット内の要素の数です。これは、n 個の要素を持つセットのパワーセットには 2^n 個のサブセットが含まれるためです。

ジェネリックとセットを使用した getPowerset 関数の実際の実装は次のとおりです。

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<Set<T>>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<T>());
        return sets;
    }
    List<T> list = new ArrayList<T>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
    for (Set<T> set : powerSet(rest)) {
        Set<T> newSet = new HashSet<T>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }       
    return sets;
}  
ログイン後にコピー

Test

与えられた例で getPowerset 関数をテストしてみましょうinput:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : powerSet(mySet)) {
     System.out.println(s);
}
ログイン後にコピー

これにより、次の出力が表示されます:

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
ログイン後にコピー

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

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