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

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

给定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、1

设置2和3:9、11

设置1、2和3:11

我正在考虑先找到所有可能的集合组合,然后使用一种算法来找到此处找到的n个集合的交集。不过,我担心这种方法的时间效率。

如果您能找到比我幼稚的方法更好的方法,那么用伪代码回答将是最有帮助的。

回答:

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

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

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

如果您希望使用真实的map-

reduce分配计算,则第一个映射将映射到element的键和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的交集中。)

以上是 n个集合的所有组合的交集 的全部内容, 来源链接: utcz.com/qa/425340.html

回到顶部