Лучший алгоритм для сравнения набора с набором наборов
Каков наилучший алгоритм для нахождения наборов в конечном наборе наборов, которые являются подмножеством определенного набора?
Например, если
A = {1, 2}
B = {2, 3, 4}
C = {3, 5}
D = {6}
и Х = {1, 2, 3, 5}
Тогда A и C являются подмножествами X.
Есть ли алгоритм, который я мог бы сделать это в линейной сложности времени?
Примечание по реализации: Члены наборов, как правило, принадлежат к очень ограниченному диапазону, поэтому было бы неплохо использовать битовый набор C ++ для реализации алгоритма. Не так ли?
Редактировать: Количество наборов в коллекции, как правило, намного больше, чем количество элементов в X (в примере). Есть ли способ сделать это линейным с точки зрения количества элементов в X? Вероятно, используя хэш или что-то?
Решение
Предположим на минуту 64 возможных элемента.
Затем, если вы представляете каждый элемент как бит, вы можете использовать 64-битное целое число для представления каждого набора, а затем: a & b это установить пересечение из a а также b,
Если и только если) a это подмножество b затем a & b == a,
Конечно, вы можете использовать набор битов, если вам нужно более 64 бит.
Для большого диапазона элементов, используя хеш-таблицу для хранения (один раз) надмножества, а затем итерируя потенциальные подмножества, чтобы проверить, все ли элементы в нем, можно сделать.
Он является линейным по размеру ввода (средний случай).
РЕДАКТИРОВАТЬ: (ответ на отредактированный вопрос)
Если вы предварительно не сохранили некоторую информацию о данных — это нельзя сделать лучше O(|X| + n*min{m,|X|}) Где | X | это размер множества X, n это количество комплектов, и m средний размер наборов
Причина этого заключается в том, что в худшем случае вам нужно прочитать все элементы во всем наборе (потому что последний элемент, который вы читаете для каждого набора, решает, является ли он подмножеством или нет), и, таким образом, мы не сможем добиться лучшего без предшествующего знания о наборы.
Предлагаемые решения:
BITSET: O(|X|*n)
Хеш-решение: O(|X| + min{m,|X|}*n) (средний случай)
Хотя хеш-решение обеспечивает лучшую асимптотическую сложность, константы намного лучше для набора битов, и, таким образом, решение для набора битов, вероятно, будет быстрее для малых |X|
Другие решения
Если вы не ограничены во времени для создания некоторых дополнительных структур, решение O (log (n)) будет хранить последовательности битов, которые представляют отдельные наборы в Trie.
Вам не нужно сравнивать ваш набор (a.k.a. bitstring) со всеми другими наборами, как предполагает Амит. Если у вас есть отсортированная коллекция цепочек битов, то каждое сравнение, очевидно, уменьшает количество вариантов в два раза. Да, конечно, время для создания набора битов — это что-то вроде O (n * log (n)), но это предварительная обработка.