n个集合的所有组合的交集 [英] The intersection of all combinations of n sets

问题描述

我需要帮助找到解决该问题的有效算法：

I need help finding an efficient algorithm to solve this problem:

给出n个未排序的整数集，找到n及其相交的所有可能组合。

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

例如：



输入（n = 3）：

For example:

Input (n=3):

设置1 = 1，10，6，11，14，3

设置2 = 3，7，11，9，5

设置3 = 11，6 ，9、1、4

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

输出：

设置1& 2：3，11

第1集& 3：1，6

第2集& 3：9，11

设置1，2，& 3：11

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

我在想先找到所有可能的集合组合，然后使用一种算法找到找到的n个集合的交集此处。但是，我担心这种方法的时间效率。

I was thinking of first finding all possible combinations of sets and then using an algorithm to find the intersection of n sets found here. I'm worried about the time efficiency of this approach, though.

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

If you can find something better than my naive approach, an answer in pseudo-code would be most helpful.

推荐答案

此处是受 http://research.google.com/archive/mapreduce.html （因此，可以根据需要以分布式方式编写）。

Here is a solution inspired by http://research.google.com/archive/mapreduce.html (which can therefore be written in a distributed way if you want).

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

Map all of your elements in sets to pairs [element, set]. Group this list by element. (You can just sort and pull out elements. Or you can create a hash of arrays whose keys are the elements and values are the list of sets that element is found in.) Then for each element, emit a list of [combination of sets, element]. Group that by combination. And now for each non-empty combination, you can just read off the elements in it.

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

If you wish to distribute the computation with a real map-reduce, the first map would map to a key of element, and value of set. The first reduce would just store by element the list of sets it is in. The second map would emit for each element one key for each combination of sets it is in, with the element as the value. And the second reduce would store your final answer.

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

It may help to work your example in detail. You start with:

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],

现在按元素分组（我通过排序手动完成）以获得：

Now group by element (I did it by hand by sorting) to get:

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

现在，我们开始第二个映射（跳过仅位于一组中的元素）以获取：

And now we do the second mapping (skipping the elements that are only in one set) to get:

[(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]

通过集合组合进行分组，我们得到：

Group that by combination of sets and we get:

(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的交集上。）

(This differs from your suggested answer because you missed that 11 is in the intersection of sets 1 and 3.)

这篇关于n个集合的所有组合的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！