arrays - 算法:从数组中找到最大的子集

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 != ∅ 则返回 true 否则返回 false。
解决它的一种方法是使所有可能的对数组，并检查它们的共性。但这里的问题是，给定一个包含共同元素的对列表，如何构造最大的子集。
例如给定上面的例子，如何从 (a1,a2), (a1,a4), (a2,a4), (a3,a4) 构造 {a1,a2,a4}。

Answer 1

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

对于问题中的示例， map 看起来像这样:

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)是所需的结果。