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个集合的交集.不过,我担心这种方法的时间效率.

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

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的交集中.)