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

Java のパワーセットを理解する

セットのパワーセットは、空のセットや元のセットを含む、その要素の可能なすべてのサブセットを表します自体。 n 個の要素を含むセットの場合、そのパワーセットは 2^n 個の一意のサブセットで構成されます。

パワーセットを効率的に取得する

Java では、次の値を計算する関数 getPowerset を定義できます。特定のセットのパワーセット。この演算の最適な時間計算量は O(2^n) です。ここで、n は入力セット内の要素の数です。

ジェネリックと再帰を使用した実装

次の実装では、ジェネリックを利用して任意のセットを操作します。 type:

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;
}

使用法と例

この関数を使用するには、セットをインスタンス化し、それを引数として getPowerset に渡します。たとえば、入力例:

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

これにより、指定されたセットのパワーセットが期待される形式で出力されます。

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