Допустим, у меня есть несколько «известных» наборов:
1 {a, b, c, d, e}
2 {b, c, d, e}
3 {a, c, d}
4 {c, d}
Мне нужна функция, которая принимает набор в качестве входных данных (например, {a, c, d, e}) и находит набор, который имеет наибольшее количество элементов, и не имеет других общих элементов. Другими словами, подмножество с наибольшим количеством элементов. Ответ не должен быть правильным подмножеством. Ответ в этом случае будет {a, c, d}.
РЕДАКТИРОВАТЬ: приведенный выше пример был неправильным, теперь исправлено.
Я пытаюсь найти самый эффективный способ сделать это.
(Ниже я предполагаю, что стоимость сравнения двух наборов O (1) ради простоты. Эта операция вне моего контроля, поэтому нет смысла думать об этом. Правда, это будет зависеть от мощности двух сравниваемых множеств.)
Кандидат 1:
Генерация всех подмножеств ввода, затем итерация по известным наборам и возвращение наибольшего, которое является подмножеством. Недостатком этого является то, что сложность будет примерно равна O (n! & Times; m ), где n - количество элементов входного набора, а m количество «известных» подмножеств.
Кандидат 1a (спасибо @bratbrat):
Переберите все «известные» множества и вычислите мощность пересечения, и возьмите тот, который имеет наибольшее значение. Это будет O (n) , где n - количество подмножеств.
Кандидат 2:
Создать обратную таблицу и вычислить евклидово расстояние между входом и известными наборами. Это может быть довольно быстро. Я не понимаю, как я мог ограничить это, чтобы включить только подмножества без последующего фильтра O (n) .
Кандидат 3:
Переберите все известные множества и сравните с входными данными. Сложность будет O (n) , где n - количество известных наборов.
В моем распоряжении набор функций, встроенных в Python и Redis.
Ничто из этого не кажется особенно великим. Идеи? Количество наборов может быть большим (около 100 000 в расчете).