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 サイトの他の関連記事を参照してください。