以有效的方式查找 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} 的 PowerSet:

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

Answer 1

尝试另一种方法：

let call set3 = set - set2;

然后 Powerset(set) - Poserset(set2) = Powerset(set3) x (Powerset(set)- {});

其中 x 是 2 集的笛卡尔倍数。

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

哈。

Answer 2

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

Answer 3

为了从一个幂集减去另一个幂集，扣除的幂集计算是多余的。方法如下：

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)) 以获取示例中的结果。

Answer 4

如果从 P(A) 中删除 P(B) 后，一组是另一组的子集（A、B 大小为 m、n），则有 2ⁿ - 2^m 元素，如果 B 不是 A 的子集，您也可以假设 B'=A 与 B 的交集，我们也有类似的关系，所以数字总体上很大。

例如假设 AB 有一个元素 |P(A)-P(B)| = 2ⁿ - 2^(n-1) = 2^(n-1)，例如，对于 n = 40，您无法迭代超过所有项目。

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

有一个以 2 为基数、大小为 n 的计数器，首先将 m+1 位设置为 1，将所有其他位设置为 0，然后打印结果，然后每次增加计数器（加一）并打印结果最多为 2^{n - 1}。其时间复杂度为 O(2ⁿ - 2^m)。