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

Question

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

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

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

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

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

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

Answer 1

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

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

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

Следующая оптимизация, которая приходит на ум, заключается в создании в индексе элементов. Таким образом, для каждого входящего набора вы найдете пересечение каждого набора, содержащего каждый из элементов. Другими словами, если для входящего набора {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

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

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

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

Answer 3

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

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

Например:

, если [ABCD] -> [2 3 5 7], р (ABC) = 30, р (ABD) = 42, р (BC) = 15, р (ABCD) = 210

Answer 4

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

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

---

@ Stephen C: поиск факторов Произвольное число действительно 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, если вы дойдете до конца коллекции. Будет работать массив BigNums.

---

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