У меня есть примерно 300 000 (300 КБ) наборов, каждый из которых содержит 0-100 элементов.
s1={a,b,x,y}
s2={a}
s3={a,x,y}
s4={x,y}
Мой вопрос: как мне эффективно найти коллекцию наборов (скажем, мне нужна коллекция из 5000 наборов изНаборов по 300 тыс.) Где максимальный уровень пересечения элементов среди этих выбранных наборов?
т.е.
Среди всех возможных комбинаций из 5000 наборов, которые можно выбрать из наборов по 300 тыс., Мне нужна одна коллекция из 5000 наборов, такая что пересечение (числообщих элементов) среди его 5000 наборов больше (> =), чем у любой другой комбинации из 5000 наборов, которые возможны из 300К наборов.
Например: из наборов, показанных выше,
Скажем, мне нужно 2 набора, где между ними есть максимальное пересечение элементов. Результирующий набор будет -> C= {s1, s3} с [общими элементами = {a, x, y}, общим количеством элементов = 3]
Скажем, мне нужно 3 набора, где максимальное пересечение элементов междуих. Результирующий набор будет -> C = {s1, s3, s4} с [общие элементы = {x, y}, общее количество элементов = 2]
Метод грубой силыне вариант, так как общее число возможных комбинаций из 5000 наборов из набора по 300 КБ огромно.
300K choose 5000 = O(10^11041)
Существуют ли какие-либо интеллектуальные структуры данных и алгоритмы, которые я могу использовать для получения желаемой коллекции наборов?
Кроме того, есть ли какая-либо библиотека Python, которую я могу использовать для этого?