Эффективный способ нахождения подмножеств и надмножеств в наборе множеств

Question

Есть ли эффективный алгоритм или структура данных для поиска надмножеств и подмножеств в наборе множеств?

Пример:

# collection of sets 
>>> col = [{1,2,3},{2,3,4},{4,5,6,7}] 

>>> subsets_of({1,2,3,4}, col) 
[{1,2,3},{2,3,4}] 

>>> supersets_of({4}, col) 
[{2,3,4},{4,5,6,7}] 

Answer 1

Вы можете создать метод хэширования для подмножеств, а затем сохранить его в HashMap.

Тогда вы можете найти его даже в постоянное время (если у вас достаточно памяти).

Answer 2

В общем случае нет, кроме методов поиска грубой силы.

Однако существуют различные методы для выполнения линейного поиска времени в зависимости от типа данных, которые у вас есть. Например, если значения элемента всегда были меньше 32 (или 64), тогда вы могли бы создать целое число с битами, установленными для имеющихся значений, и ИЛИ, чтобы они узнали, является ли набор подмножеством. Если значения меньше 100 миллионов или около того, вы можете создать гигантский логический массив, где каждый элемент массива равен 1, если набор содержит значение, или 0, если это не так. Тогда поиск подмножества является линейным временем. Аналогичный метод возможен для решения задачи надмножества в линейном времени.