计算亚群的独特交集 [英] Computing unique intersections of subsets

问题描述

给定一组的取值的= {S <子>我：{Z <子>Ĵ：Z＆ISIN代码; N 的}}，什么是时间有效的算法来计算的取值的？

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?

有关背景，我处理的几个版本这个问题，一些比别人更大。在最小的一个| 取值的| ＆asymp; 1000，| S <子>我 | ＆asymp; 10000，值为zip codeS。

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}}

| 取值的| = 4，并且有2 ⁴ 的取值 = 16的子集。 但是，也有仅五个唯一子集的交叉点集。前四个是的取值的自己成员。第五个是{3}。空集已经是取值的一员。所有其他的10集十字路口产生空集也。

|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.

推荐答案

下面是一个快速preprocessing一步，可能是值得的。

Here's a fast preprocessing step that might be worthwhile.

呼叫元素x和y的等效的，如果，对于每一个组S <子>我，或者两者或既不x和y属于为s <子>我 。通过删除除一重$ P $每个等价类的psentative所有元素简化问题。最后，展开每个重presentative同级车。

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添加映射到新的标签。

To simplify, scan sets one by one while maintaining a map from each element to a label for its equivalence class, where equivalence is determined with respect to the sets processed so far. Initially, all elements are in the same class, so this map sends each element to the same label. To process a set, initialize an empty map of new labels. For each element x in the set, let k be x's current label. If the key k exists in the new label map, then the value corresponding to k becomes x's new label. Otherwise, we allocate a new label and assign it to x and add a mapping from k to the new label.

下面是您的输入执行。

1. 最初标记= {1：一，2：3：一，4：一，5：6：一，7：一，8：一，9：一，10：一个}
2. 在扫描{}。什么也没有发生。
3. 在扫描{1}。更改标签[1]为b。
4. 在扫描{2,3}。更改标签[2]和标签[3]到c。
5. 扫描{3，4，5，6，7，8，9，10}。更改标签[3] D和标签[4..10]步骤e。
6. 在结束时，标签= {1：B，2 C，3：D，4：即5：即6：E，7：即8：即9：E，10：电子} 。选择1（b）和2（c）和3（d）和图4（e）重新present其类。所有的人都将被删除。

这篇关于计算亚群的独特交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！