python - 找到一组集合，使得所选集合之间的元素交集最大

Question

我有大约 300,000 (300K) 个集合，每个集合包含 0-100 个元素。

s1={a,b,x,y}
s2={a}
s3={a,x,y}
s4={x,y}

我的问题是，我如何有效地找到一组集合（比如我需要从 300K 集合中收集 5000 个集合），其中这些选定集合之间的元素交集最大？
即
在可以从 300K 集合中挑选的 5000 集合的所有可能组合中，我需要一个 5000 集合的集合，使得它的 5000 集合中的交集（公共元素的数量）大于（>=）5000 集合的任何其他组合可以从 300K 套中获得。

例如：从上面显示的集合中，

• 假设我需要 2 个集合，其中元素之间存在最大交集。结果集合将是 -> C = {s1,s3} 与 [common elements={a,x,y}, common elements count=3]

• 假设我需要 3 个集合，其中元素之间存在最大交集。结果集合将是 -> C = {s1,s3,s4} 与 [common elements={x,y}, common elements count=2]

Bruteforce 方法不是一种选择，因为来自 300K 集合的 5000 集合的可能组合的总数是巨大的。

300K choose 5000 = O(10^11041)

是否有任何智能数据结构和算法可用于获取所需的集合集合？

另外，是否有任何可用的 python 库可供我使用？

标签： pythonalgorithmdata-structuressetset-intersection