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

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

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

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

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

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

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

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

使用法と例

この関数を使用するには、セットをインスタンス化し、それを引数として 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);
}</integer></integer>

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

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