计算子集的唯一交集

Question

给定一个集合 S = {s_i : {z_j : z ∈ N} }，有什么时间高效的算法可以计算出 S 的子集的唯一交集集合？

背景：我正在处理几个版本的这个问题，有些比其他的要大。在最小的问题中，|S| ≈ 1,000，|s_i| ≈ 10,000，值是邮政编码。

为了清晰起见，以下是一个简单的示例：

输入: S = {{},{1},{2,3},{3,4,5,6,7,8,9,10}} 输出: {{},{1},{2,3},{3,4,5,6,7,8,9,10},{3}} |S| = 4，有 2⁴ = 16 个 S 的子集。然而，只有五个唯一的子集交集集合。前四个是 S 的成员。第五个是 {3}。空集已经是 S 的成员。其余的 10 个子集交集集合也产生空集。

- Sim

---

@amas，S有2^n个子集，且S的元素超过1000个。O(n)交集算法无济于事。在我看来，交集并不是问题，问题在于决定哪些交集不需要进行。 - Sim

@amas 我不确定你需要哪些其他细节。如果你取S的所有2^|S|个子集并将它们相交，那么在2^|S|个结果中会有很少的唯一集合。我正在寻找这些唯一的集合。 - Sim

@HighPerformanceMark 我的问题是要求子集的唯一交集（复数形式），但我听到了你的意见并添加了一个例子。 - Sim

@Sim 给出一个示例，展示输入和期望的输出。 - Khaled.K

你如何定义“子集”和“交集”？例如，S1 = {{1}, {2,3}} 和 S2 = {{}, {1}, {2,3}} 是 S 的子集，它们的交集是 (S1 & S2) == {{1}, {2,3}}，即交集的成员本身就是集合，因此交集的集合是集合 S 的子集的交集的集合（即 S 的成员的交集的集合）。你如何使输出只是一个集合的集合？ - jfs

Answer 1

这里有一个快速的预处理步骤可能是值得的。

如果对于每个集合s_i，x和y都属于s_i或者都不属于s_i，则称元素x和y为等价的。通过删除除了每个等价类的一个代表元素之外的所有元素来简化问题。最后，将每个代表扩展到其等价类。

为了简化问题，一边扫描集合，一边维护从每个元素到其等价类的标签的映射，其中等价性是相对于已处理的集合确定的。最初，所有元素都在同一类中，因此该映射将每个元素发送到相同的标签。要处理一个集合，请初始化一个新标签的空映射。对于集合中的每个元素x，让k是x的当前标签。如果新标签映射中存在关键字k，则对应于k的值成为x的新标签。否则，我们分配一个新标签并将其分配给x，并添加从k到新标签的映射。

以下是输入的执行过程。

1. 最初的标签为{1: a, 2: a, 3: a, 4: a, 5: a, 6: a, 7: a, 8: a, 9: a, 10: a}。 2. 扫描{}。什么也不发生。 3. 扫描{1}。将label[1]更改为b。 4. 扫描{2, 3}。将label[2]和label[3]更改为c。 5. 扫描{3, 4, 5, 6, 7, 8, 9, 10}。将label[3]更改为d，将label[4..10]更改为e。 6. 最后，label = {1: b, 2: c, 3: d, 4: e, 5: e, 6: e, 7: e, 8: e, 9: e, 10: e}。选择1（b）和2（c）和3（d）和4（e）来代表它们的类。其他所有元素都被删除。

- David Eisenstat

---

有趣。它并没有解决问题，但是它给了我一个处理整个问题的不同方法的好主意，所以我会接受这个答案。 - Sim

Answer 2

渐近时间复杂度：

n：集合数量，在执行过程中会发生变化

m：平均集合大小

时间：T（搜索匹配集）x T（交集）x SUM { k }，其中 k:1..n

时间：2m x 2m x 1/2 n(n+1)

时间：O（4 m^2 x 1/2 n x (n+1)）~ O(n^2 m^2)

提出的算法：

FOR i: 1..n
{

    FOR j: i..n
    {

        IF i = j THEN SKIP

        INTERSECTION := FIND-INTERSECTION ( SETS[i], SETS[j] )

        IF INTERSECTION ⊄ SETS[] THEN ADD INTERSECTION TO SETS[]

    }

}

- Khaled.K