java - 以有效的方式查找 PowerSet 的一组特定子集

Question

我正在尝试寻找一种有效 的方法来获取 PowerSet 的一组子集。

例如，这在集合尺寸较小时有效:

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

Set<Integer> set2 = new HashSet<Integer>();
set2.add(3);


Set<Set<Integer>> sets = MyUtils.powerSet(set); //size - 8 SubSets
Set<Set<Integer>> badSets = MyUtils.powerSet(set2); //size - 2 SubSets

//my set of subsets of the powerset
sets.removeAll(badSets) //size - 6 SubSets

然而，当更多元素被添加到这些集合中时，这并不实用。还有其他方法吗？

只是友好地提醒一下 PowerSet 是什么:

{a,b,c} 的幂集:

P(S) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

Answer 1

如果从 P(A) 中删除 P(B) 后，一组是另一组的子集(A、B 大小为 m、n)，则有 2ⁿ - 2^m 元素，如果 B 不是 A 的子集，您可以再次假设 B'=A intersection with B 并且我们有类似的关系，所以数字都很大。

例如假设 A-B 有一个元素，|P(A)-P(B)| = 2ⁿ - 2^(n-1) = 2^(n-1)，例如对于 n = 40 你不能迭代在所有项目上。

无论如何，一种方法如下:

有一个大小为 n 的计数器，以 2 为底，首先将 m+1 位设置为 1，将其他所有设置为 0 然后打印结果，每次增加计数器( 1) 并打印结果 upto rich to 2^{n - 1}。这是 O(2ⁿ - 2^m).