algorithm - n 组之间的最大交集

Question

我有 x 个集合，每个集合中有 y 个元素(未排序的整数)。我想找到这对集合之间的最大交集大小。

例如:

*5 sets, size = 3

set 1 : 1 2 3

set 2 : 4 2 3

set 3 : 5 6 7

set 4 : 5 8 9

set 5 : 5 10 11

集合 1 和集合 2 的最大交集大小为 2；答案是 2。

因此，我可以使用 HashSets 在 O(x^2 * y) 中完成此操作，只需查看所有对并计算它们的交集大小。但我想做得更快。我认为有特定的算法或数据结构可以提供帮助。你能给我一些想法吗？

更新:x 和 y 大约是 10^3，元素是 int。并且没有相等集。

Answer 1

我能想到的一个优化是记住第一组和其余组之间的交集大小，然后使用数据来减少一些情况。

如何使用它:

如果你有集合 A , B , C长度n和

intersection(A,B) = p
intersection(A,C) = q

然后

intersection(B,C) <= n - abs(p - q)

对于您的案例中的集合:

S0 = { 1 2 3 }
S1 = { 4 2 3 }
S2 = { 5 6 7 }

你计算intersection(S0,S1) = 2并记住结果:

[ i(0,1)=2 ]

然后 intersection(S0,S2) = 0 , 所以

[ i(0,1)=2; i(0,2)=0 ]

当你计算 intersection(S1,S2) 时比较第一个元素后

(S1[0]=4 != S2[0]=5)

你可以说intersection(S1,S2) <= 2这是迄今为止最好的结果。

可以进一步改进的是记住更准确的交集结果，但仍然不会计算所有结果。

我不确定这是否是最佳选择。也许存在完全不同的方法。