Содержит superset

Question

Я нахожусь в поиске структуры («набора множеств»), которая позволила бы мне эффективно проверить, содержит ли она надмножество моего набора.

Пример: А = {1, 2} В = {2, 3} С = {1, 3} D = {1, 2, 3}

набор множеств S1 = { а, в}, а другой S2 = {D}

S1 contains A => true 
S1 contains C => false 
S2 contains A => true 

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

Answer 1

Используйте словарь для преобразования между различными отдельными элементами и позициями в растровом изображении. Затем сохраните каждый набор в виде растрового изображения.

Возьмем объединение множества множеств - это вопрос об объединении бит-карт.

Проверка того, является ли один набор подмножеством набора наборов, проверяет соответствие бит-бит в растровом изображении меньшего набора.

Эти операции должны быть быстрыми. И если вы были действительно амбициозных, вы можете начать с http://en.wikipedia.org/wiki/General-purpose_computing_on_graphics_processing_units и выяснить, как переместить вычисления на GPU.

Если у вас были большие наборы и были в порядке, иногда получая неправильный ответ, тогда вы должны искать Bloom Filters. Это позволяет получить в основном правильные ответы со значительно более короткими растровыми изображениями.