n个集合的所有组合的交集

n个集合的所有组合的交集

这是一个受http://research.google.com/archive/mapreduce.html启发的解决方案（因此，可以根据需要以分布式方式编写）。

将集合中的所有元素映射为对

[element,set]

。将此列表按元素分组。（您可以对元素进行排序和提取。也可以创建数组的哈希，其键是元素，值是在其中找到元素的集合的列表。）然后，对于每个元素，发出一个[集合的组合的列表，元素]。通过组合将其分组。现在，对于每个非空组合，您都可以读取其中的元素。

如果您希望使用真实的map-
reduce分配计算，则第一个映射将映射到element的键和set的值。第一个reduce将仅按元素存储其所在的集合列表。第二个映射将针对每个元素针对其所在的每个集合组合发射一个键，并以元素作为值。第二个减少将存储您的最终答案。

这可能有助于详细处理您的示例。您从开始：

Set 1 = 1, 10, 6, 11, 14, 3Set 2 = 3, 7, 11, 9, 5Set 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 33: Set 1, Set 24: Set 35: Set 26: Set 1, Set 37: Set 29: Set 2, Set 310: Set 111: Set 1, Set 2, Set 314: 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

（这与您建议的答案不同，因为您错过了11位于集合1和3的交集中。）