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

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 (m log (n)), конечно, уменьшается до O (m log (n)).

Answer 2

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

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

---

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

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

Для каждой существующей записи E в наборе множеств остановите, если p (S)

p (E) и p (E) делит p (S) точно. Добавьте S, если вы дойдете до конца коллекции. Массив BigNums будет работать.

---

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

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

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

• храните наборы так, как вы хотите
• сохранить карту set_id -> set_size
• сохранить карту объекта -> set_id

и A, и B являются O (K).