3

给定一个集合S = {s i : {z j : z ∈ N } }，计算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}}

| 小号| = 4 并且有 2 4 = 16 个S的子集。但是，只有五组独特的子集交集。前四个是S本身的成员。第五个是{3}。空集已经是S的成员。所有其他 10 个子集交集也产生空集。

4

2 回答 2

2

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

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

为简化起见，一个一个地扫描集合，同时维护从每个元素到其等价类的标签的映射，其中等价性是相对于迄今为止处理的集合确定的。最初，所有元素都在同一个类中，因此此映射将每个元素发送到相同的标签。要处理一个集合，请初始化一个新标签的空映射。对于集合中的每个元素 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}。将标签 [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) 来表示他们的类。所有其他都被删除。
于 2013-04-04T13:30:10.453 回答
0

渐近时间复杂度：

n：集合的数量，在执行过程中会改变

m：平均集合大小

时间： T(Search-Matching-Sets) x T(Intersection) x SUM { k } for k: 1..n

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

时间： O(4 m^2 x 1/2 nx (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[]

    }

}
于 2013-04-04T08:34:21.217 回答