Коллекция наборов, не содержащих наборов, которые являются подмножеством другого в коллекции

Question

Я ищу абстрактную структуру данных, которая представляет собой набор наборов таким образом, чтобы ни один набор в коллекции не был подмножеством другого набора в коллекции.

Это означает, что при вставке будут выполнены следующие условия:

A.Вставка элемента, который уже является подмножеством другого элемента, вернет исходную коллекцию.

B.Вставка элемента, который является надмножеством любых других элементов, приведет к созданию коллекции с добавлением надмножества и удалением подмножеств.

Предполагая упорядоченность элементов набора, тогда для представления коллекции можно использовать дерево префиксов.Это позволяет выполнять условие A очень быстро (т. е. Проверка условия не занимает больше времени, чем вставка подмножества), однако выполнение условия B требует времени.

Мне интересно, существует ли структура данных, которая также позволяет быстро выполнять B.

Answer 1

Тривиальным подходом было бы сохранить список наборов и выполнить линейный поиск по нему для каждого входящего набора (проверяя, является ли входящий подмножеством).

Очевидно, что это выполняется за O (n) время для линейного поиска и, возможно, за O (m) размер для размера входящего набора.Таким образом, O (n * m) общее время (количество сетов по сравнениюразмер каждого набора).

Наиболее очевидной оптимизацией, конечно, является индексирование по заданным размерам.Затем вы тестируете каждый входящий набор только с теми, которые имеют одинаковый или больший размер.(Набор не может быть подмножеством любого меньшего набора, да!).

Следующая оптимизация, которая приходит на ум, - это создание в индексе элементов.Таким образом, для каждого входящего набора вы бы нашли пересечение каждого набора, содержащего каждый из элементов.Другими словами, если для входящего набора {a, b, c} мы обнаружим, что элемент {a} существует в наборах A, B и D, элемент {b} существует в B, E и F, а {c} существует в A, B и Z...тогда входящий набор является подмножеством B (пересечение {A, B, D}, {B, E, F} и {A, B, Z}).

Итак, для меня это звучит как сложность O (m * log (n)).(Мы должны выполнить хэшированный поиск по каждому элементу каждого входящего набора).Вставки также должны выполняться в том же порядке (вставка идентификатора нового набора в каждую из карт элемента).(В анализе Big-O 2*O(mlog(n)) уменьшается до O(mlog(n)), конечно).

Answer 2

Тривиальная идея, которая будет работать в O (K), где K - размер добавляемого элемента.

• храните наборы любым удобным для вас способом
• сохраните карту set_id -> set_size
• сохранить карту объекта -> set_id

и A, и B равны O(K).

Answer 3

Если отдельные члены ваших множеств A, B, ...сопоставляются с различными (и относительно) простыми числами, и рядом с каждым набором вы сохраняете произведение всех членов как p (A), p (B) и т.д.тогда подмножества и надмножества можно найти по тому, является ли p (X) коэффициентом p (Y) или наоборот.

Я думаю, в итоге у вас могло бы получиться несколько очень больших чисел, но теоретически это работает.

Например:

если [a b c d] -> [2 3 5 7], p(abc) = 30, p(abd) = 42, p(bc) = 15, p (abcd) = 210

Answer 4

Какой придурковатый сайт!Сейчас я зарегистрировался, так что, возможно, со временем смогу прокомментировать вчерашний материал.Однако до тех пор...

@Стивен Си:хотя я считаю, что мой английский достаточен, я, кажется, приобрел объяснение:однако он кое-что упустил, и его комментарий должен звучать следующим образом:

---

@Стивен Си:нахождение множителей произвольное число действительно является NP полным, но здесь не имеет значения.Проблема заключается в том, точно ли меньшее из двух чисел делит большее, простая операция с модулем.Например, p(bc)=15 является делителем p (abcd)= 210, таким образом, bc является подмножеством abcd (как и множества abd и abc).

Добавление нового набора S к существующей коллекции из N наборов равно O(N), предполагая, что сравнение и деление больших чисел занимает примерно одинаковое время независимо от N.

Для каждой существующей записи E в коллекции наборов остановитесь, если p(S) < p (E) и p (S) точно делят p (E).Если p(S) = p(E), остановитесь.Удалите E, если p (S) > p (E) и p (E) точно делит p (S).Добавьте S, если вы дойдете до конца коллекции.Массив больших чисел подошел бы.

---

@JL:если вы хотите быть моим преследователем на сайте, пожалуйста, постарайтесь 1) повысить ценность 2) точно.