的n所有组合的交集

Question

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

给定n无序整数集，发现n和它们的交叉点的所有可能的组合。

例如：

输入（N = 3）：

集1 = 1，10，6，11，14，3
组2 = 3，7，11，第9， 5
集3 = 11，6,9，1,4-

输出：

组1 & 2：3，11
集1 & 3：1，6
集2 & 3：9,11
集1，2，& 3：11

我想的首先找到的组的所有可能组合，然后使用一种算法来找到n组相交发现here。不过，我担心这种方法的时间效率。

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

Answer 1

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

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

如果您希望使用真实的map-reduce分配计算，则第一个映射将映射到元素的键和set的值。第一个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 

（这不同于你所建议的答案，因为你错过了11中的1套的交集和3）

Answer 2

使用你的榜样，只是注意

1 N 2 N 3

也

（1 N 2）N 3

所以如果你缓存你的（1 n 2）解决方案，你可以重新使用它，这样计算1 n 2 n 3只会需要一个额外的交点计算。一般来说，如果您的例子中有四种可能的组合，那么如果您保存并重新使用之前的结果，最终只需要完成四个交叉。