Поиск наборов, которые являются подмножеством определенного набора

Question

Допустим, у меня есть 4 разных значения A, B, C, D с прикрепленными наборами идентификаторов.

А = {1,2,3,4,5}
В = {8,9,4}
С = {3,4,5}
D = {12,8}

И учитывая набор S идентификаторов {1,30,3,4,5,12,8} Я хочу, чтобы он возвращал C и D. т.е. извлекал все наборы из группы наборов, для которых S является надмножеством.

Существуют ли алгоритмы для эффективного выполнения этой задачи (желательно с низкой сложностью памяти. Использование внешнего устройства для хранения данных не вариант)? Тривиальным решением было бы для каждого члена в расширенном наборе S получить список наборов, которые включают этот элемент (в основном инвертированный индекс), и для каждого возвращенного набора проверить, что все его члены находятся в расширенном наборе. К сожалению, поскольку в среднем надмножество будет включать в себя хотя бы одного члена для каждого набора, при таком подходе будет существенное и недопустимое снижение производительности.

Я пытаюсь сделать это на Java. Набор состоит из целых чисел, и значение, которое они идентифицируют, является объектом. Коллекция наборов не является статичной и должна меняться в процессе исполнения. Там будет некоторое ограничение на установленное количество, хотя. Размер набора не ограничен. Но в среднем это от 1 до 20.

Answer 1

1. Пройдите через каждый элемент x in S .
2. Для каждого набора t , для которого x ∈ t , увеличить счетчик - назовите его t _count - связанный с t .
3. После всего этого для каждого набора t , для которого t _count = | т |, вы знаете, что т ⊆ S .

Применение.

После шага 2.

A _count = 4,
B _count = 1,
C _count = 3,
D _count = 2.

Шаг 3. Обработка.

A _count ≠ | A | (4 ≠ 5) - Отклонить,
B _count ≠ | B | (1 ≠ 3) - Отклонить,
C _count = | C | (3 = 3) - Принять,
D _count = | D | (2 = 2) - Принять.

Answer 2

Примечание после примечания cgkanchi: Следующий алгоритм предполагает, что вы на самом деле не используете наборы, а массивы. Если это не так, вы должны искать метод, который реализует пересечение множеств, и тогда проблема тривиальна. Это о том, как реализовать понятие пересечения с использованием массивов.

1. Сортировка всех наборов с использованием heapsort для сортировки по месту O (1). Он запускается в O (nlogn) и довольно скоро он окупит вас.

2. Для каждого набора L из всех наборов:

   2,1. j = 0

   2,2. Для элемента i в L:

   2.2.1. Начиная с j элемент найти L[i] в S, для которого L[i] = S[j] еще отклонить. Если L и S и достаточно велики, используйте бинарный поиск или интерполяционный поиск (для второго взгляните на распределение данных)

   2,3. Accept

Answer 3

Что касается Java, я бы использовал Hashtable для таблицы поиска элементов в S . Затем для каждого элемента в X набор, который вы хотите проверить, если он является подмножеством S , проверьте, находится ли он в справочной таблице. Если все элементы X также находятся в S , то S является расширенным набором X .