Let $A$ be a finite set, and $S \subset \mathcal{P}(A)$.
Is there a data structure for $S$ that would allow to quickly retrieve an element $q \in S $, given a key $p \in \mathcal{P}(A)$, such that $q$ is (one of) the smallest superset(s) of $p$?
The assumption is that $A$ is relatively small and that the elements in $S$ and $\mathcal{P}(A)$ are represented with binary integers, which fit within single memory words. This allows to determine their size, subset relationship, and hash values in $\mathcal{O}(1)$ time.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Possibly useful: cs.stackexchange.com/q/75915/755, cs.stackexchange.com/q/39976/755, cs.stackexchange.com/q/70405/755, cs.stackexchange.com/q/109399/755. $\endgroup$– D.W. ♦Oct 20, 2019 at 18:26
Add a comment
|