计算子集的唯一交集

Given a set S = {s_i : {z_j : z ∈ N} }, what is a time-efficient algorithm for computing the unique sets of intersections of the subsets of S?

For background, I am dealing with several versions of this problem, some larger than others. In the smallest one |S| ≈ 1,000, |s_i| ≈ 10,000 and the values are zip codes.

为了清楚起见，举个小例子：

Input: S = {{},{1},{2,3},{3,4,5,6,7,8,9,10}}
Output: {{},{1},{2,3},{3,4,5,6,7,8,9,10},{3}}
  

|S| = 4 and there are 2⁴ = 16 subsets of S. However, there are only five unique sets of subset intersections. The first four are the members of S themselves. The fifth is {3}. The empty set is already a member of S. All other 10 subset intersections produce empty sets also.

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

Call elements x and y equivalent if, for every set s_i, either both or neither of x and y belong to s_i. Simplify the problem by deleting all elements except one representative of each equivalence class. At the end, expand each representative to its class.

为了简化，一一扫描集合，同时维护从每个元素到其等价类标签的映射，其中等价性是相对于到目前为止处理的集合来确定的。最初，所有元素都属于同一类，因此此映射将每个元素发送到相同的标签。要处理集合，请初始化新标签的空映射。对于集合中的每个元素 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. 最后，标签 = {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) 来代表他们的类别。其他的都被删除。