用一种有效的方法求出幂集的一个特定子集

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是什么:

PowerSet of {a,b,c}:

p (S ) = { {}, { }, {b}, {c}, {a、b}, {a, c}, {b, c}, {a, b, c}}

Answer 1

如果一个集合是另一个集合的子集(A,B大小为m,n)从p (A)中删除p (B)后，你有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时你不能遍历所有的元素

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

有一个以2为基数的n大小的计数器，首先设置m+1位为1，所有其他为0，然后打印结果，每次增加计数器(1)并打印结果直到2^{n - 1}。O(2 <一口> n> 共舞)。

Answer 2

再试一次:

set - set2

则Powerset(set)- Powerset(set2) = Powerset(set3) x (Powerset(set)- {});

这里的x是2的笛卡尔倍数

如果set3有x元素，set2有y元素，那么用这种方法，它的复杂度大约是2^(x+y)，而如果试图直接删除它，复杂度大约是2^(x+ 2Y)。

Hth .

Answer 3

听起来像是零抑制决策图的工作。它们支持集合减法，并且在ZDD中创建一系列数字的幂集是微不足道的(事实上，最终的ZDD只有很少的节点)。这意味着非对称差异也会运行得很快，因为它在两个小的ZDD上，它只取决于节点中ZDD的大小，而不是它们包含的集合的数量。我不知道你接下来要用它做什么，但不管它是什么，你总是可以枚举ZDD中的所有集合，并把它们放在另一个数据结构中。

Answer 4

对于一个幂集减去另一个幂集，减去的幂集计算是冗余的。以下是方法:

public static <T>void removePowerSet(
        Collection <? extends Collection <T>> powerSet,
        Collection <T> removedComponents){
    Iterator <? extends Collection <T>> powerSetIter = powerSet.iterator();
    while (powerSetIter.hasNext()) {
        Collection <T> powerSetSubset = powerSetIter.next();
        if (removedComponents.containsAll(powerSetSubset)) {
            powerSetIter.remove();
        }
    }
}

对于HashSet

，该算法在多项式时间- O(n²)内执行。

现在可以调用removePowerSet(sets, set2)或removePowerSet(sets, Arrays.asList(3))来获得示例中的结果。