algorithm - n组所有组合的交集

Question

我需要帮助找到一个有效的算法来解决这个问题:

Given n unsorted sets of integers, find all possible combinations of n and their intersections. For example:

Input (n=3):

Set 1 = 1, 10, 6, 11, 14, 3
Set 2 = 3, 7, 11, 9, 5
Set 3 = 11, 6, 9, 1, 4

Output:

Set 1 & 2: 3, 11
Set 1 & 3: 1, 6, 11
Set 2 & 3: 9, 11
Set 1, 2, & 3: 11

我正在考虑首先找到所有可能的集合组合，然后使用算法找到此处找到的 n 集合的交集:Intersection of n sets .不过，我担心这种方法的时间效率。

如果您能找到比我天真的方法更好的东西，伪代码的答案将是最有帮助的。

Answer 1

这是一个受 MapReduce: Simplified Data Processing on Large Clusters 启发的解决方案，因此可以根据需要以分布式方式编写。

将集合中的所有元素映射到对[element, set]。按元素对列表进行分组。您可以对元素进行排序和提取。或者您可以创建一个数组散列，其键是元素，值是找到该元素的集合列表。然后对于每个元素，发出一个 [集合组合，元素] 的列表。按组合分组。现在对于每个非空组合，您可以只读出其中的元素。

如果您希望使用真正的 map-reduce 分配计算，第一个映射将映射到元素的键和集合的值。第一个 reduce 将按元素存储它所在的集合列表。第二个 map 将为每个元素发出一个键，用于它所在的集合的每个组合，元素作为值。第二个 reduce 将存储您的最终答案。

详细操作您的示例可能会有所帮助。你开始:

Set 1 = 1, 10, 6, 11, 14, 3
Set 2 = 3, 7, 11, 9, 5
Set 3 = 11, 6, 9, 1, 4

您将其映射到列表:

[1, Set 1], [10, Set 1], [6, Set 1], [11, Set 1], [14, Set 1], [3, Set 1],
[3, Set 2], [7, Set 2], [11, Set 2], [9, Set 2], [5, Set 2],
[11, Set 3], [6, Set 3], [9, Set 3], [1, Set 3], [4, Set 3],

现在按元素分组(我是手工排序的)得到:

1: Set 1, Set 3
3: Set 1, Set 2
4: Set 3
5: Set 2
6: Set 1, Set 3
7: Set 2
9: Set 2, Set 3
10: Set 1
11: Set 1, Set 2, Set 3
14: Set 1

现在我们进行第二次映射(跳过仅在一组中的元素)以获得:

[(Set 1, Set 3), 1],
[(Set 1, Set 2), 3],
[(Set 1, Set 3), 6],
[(Set 2, Set 3), 9],
[(Set 1, Set 2), 11],
[(Set 1, Set 3), 11],
[(Set 2, Set 3), 11],
[(Set 1, Set 2, Set 3), 11]

通过集合的组合将其分组，我们得到:

(Set 1, Set 2): 3, 11
(Set 1, Set 3): 1, 6, 11
(Set 2, Set 3): 9, 11
(Set 1, Set 2, Set 3): 11