算法：从数组中找到最大的子集

Question

我有多个阵列。我需要找到最大的数组子集，这样，该子集中的所有数组至少有一个彼此共有的元素。最大的意思是子集应该有最多的数组。我对查找子集中有哪些特定数组不感兴趣，而是对子集的大小感兴趣。例如如果：

a1 = [1,3,7]
a2 = [3,5,7]
a3 = [2,8,9]
a4 = [7,8,9]

那么我应该得到最大子集大小为 3，因为给定数组的最大子集将是 a1、a2 和 a4，因为：
a1 ∩ a2 != ∅ && a1 ∩ a4 != ∅ && a2 ∩ a4 != ∅

我有一个函数 common(array1,array2) 如果 array1 ∩ array2 != ∅ 则 returns 为真，否则为假。
解决它的一种方法是使所有可能的对数组，并检查它们的共性。但这里的问题是，给定一个具有共同元素的对列表，如何构造最大的子集。
例如给定上面的例子，如何从 (a1,a2), (a1,a4), (a2,a4), (a3,a4).

构造 {a1,a2,a4}

Answer 1

由于您对查找子集中有哪些特定数组不感兴趣，而只是查找子集的大小，因此一种方法是创建所有可能值与包含该值的数组数量的映射.

对于问题中的示例，地图看起来像：

count[1] = 1 // contained by a1
count[2] = 1 // contained by a3
count[3] = 2 // contained by a1, a2
count[7] = 3 // contained by a1, a2, a4
count[8] = 2 // contained by a3, a4
count[9] = 2 // contained by a3, a4

count 映射中的最大值（在本例中为 3）是所需的结果。

算法：从数组中找到最大的子集

Algorithm: find largest subset from arrays

arrays

algorithm

intersection