Алгоритм поиска подмножества

Предположим, у меня есть список подмножеств . Я могу сделать предварительную обработку в этом списке, если это необходимо. После этой предварительной обработки мне предоставляется другой набор . Я хочу , чтобы определить , какие - либо множества с .$\cal X$$\{1, ..., n\}$$A \subseteq \{1, ..., n \}$$B \in \mathcal X$$B \subseteq A$

Очевидный алгоритм (без какой-либо предварительной обработки) занимает время - вы просто проверяете на каждом отдельно. Есть ли что-нибудь лучше, чем это?$O(n |\cal X|)$$A$$B \in \mathcal X$

Если это поможет, вы можете предположить, что для любого общее число совпадений ограничено чем-то вроде .$A$$B \in \mathcal X$$O(1)$

Это не ответ. Это простое, но длительное наблюдение. Надеюсь это будет полезно.

Вариант решения вашей проблемы: содержит ли подмножество ?$\cal X$$A$

Эта проблема связана с проблемой оценки монотонных булевых функций от переменных. Подмножество эквивалентно битной строке, поэтому семейство эквивалентно булевой функции$n$$\{1,\ldots,n\}$$n$$\cal X$$f$ от переменных. Для данной функции можно определить наименьшую монотонную функцию, которая не больше , а именно . Исходная задача затем сводится к оценке . И наоборот, проблема оценки монотонной булевой функции может быть сведена к исходной задаче, либо наивно, если взять$n$$f$$f$$g(y)=(\exists x\subseteq y,\,f(x))$$g(A)$$f=g$или выбрав который делает меньше.$f$$\cal X$

На практике BDD имеют тенденцию работать хорошо. Таким образом, одним из возможных подходов является создание BDD для$f$ , извлечь из него BDD для и затем оценить . Средний размер BDD для должен быть , поскольку существует много монотонных булевых функций . Следовательно, в теории это плохое решение.$g$$g$$g$$\Omega\left(\binom{n}{n/2}\right)$

Но (1) возможен более качественный анализ и (2) могут быть изменения в этом подходе, которые делают его лучше. Например, я никоим образом не использовал корреляцию между размером и размером BDD . (Должна быть корреляция, но я не знаю, является ли она простой или пригодной для использования здесь.)$\cal X$$g$

Для полноты простой алгоритм для вычисления BDD для из BDD для является следующим. Здесь - стандартная операция or для BDD.$g$$f$

Возможно, вы можете использовать метод «поиска информации»: на этапе предварительной обработки построить инвертированный индекс (в вашем случае простой$n \times | {\cal X}|$ достаточно двумерного массива), который отображает элемент $x_i \in \{1,...,n\}$ к наборам в $\cal X$ которые содержат это: $inv(x_i)= \{ X_j \in {\cal X} \; | \; x_i \in X_j \}$,

Установить целочисленный массив $occ$ длины $|\cal X|$,

Тогда для каждого $y_i \in A$ извлекать $inv(y_i)$и для каждого $X_j \in inv(y_i)$ делать $occ[j] = occ[j]+1$

В конце концов, вам нужны те наборы, для которых $|X_j|=occ[j]$,

Вы можете произвольно ускорить процесс (за счет экспоненциального пространства) путем индексации двух или более элементов вместе.