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

最適な複雑さを備えた Java でのセットのパワーセットの取得

セットのパワーセットは、そのセットのすべてのサブセットのコレクションです。 n 個の要素を含むセットの場合、パワーセットには 2^n 個のサブセットが含まれます。

Java セットを考えてみましょう。

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

関数 getPowerset を作成して、次のパワーセットを生成したいと考えています。このセット。この操作の理想的な複雑さは O(2^n) です。

Java のジェネリックスとセットを使用した実装の 1 つは次のとおりです。

public static <T> Set<Set<T>> getPowerset(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 : getPowerset(rest)) {
        Set<T> newSet = new HashSet<>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }

    return sets;
}

この再帰的ソリューションは、セットの要素を反復処理します。それらを各サブセットに追加し、新しいサブセットを生成します。残りの要素のパワーセットを一貫して維持します。

入力例を使用した簡単なテストでは、期待される結果が得られます。

for (Set<Integer> s : getPowerset(mySet)) {
    System.out.println(s);
}

出力:

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

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