n组之间的最大交集

Question

我有x个集合,每个元素都有y个元素(未排序的整数).我想找到这组之间的最大交叉大小.

例如:

*5套,尺寸= 3

设置1:1 2 3

第2集:4 2 3

3:5 6 7

第4:5 8 9

第5:5 10 11

最大交点已设置1与集合2,它的大小为2; 答案是2.

所以,我可以在O(x ^ 2*y)中使用HashSets,只需查看所有对并计算它们的交点大小.但我想更快地做到这一点.我认为有特定的算法或数据结构可以提供帮助.你能给我一些想法吗？

更新:x和y大约是10 ^ 3,元素是int.而且没有平等集合.

Answer 1

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

如何使用它：

如果你有长度为A, B,的集合Cn

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这是迄今为止最好的结果。

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

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