Let X be a set of distinct 64-bit unsigned integers std::uint64_t, each one being interpreted as a bitset representing a subset of {1,2,...,64}.
I want a function to do the following: given a std::uint64_t A, not necessarily in X, list all B in X, such that B is a subset of A, when A, B are interpreted as subsets of {1,2,...,64}.
(Of course, in C++ this condition is just (A & B) == B).
Since A itself need not be in X, I believe that this is not a duplicate of other questions.
X will grow over time (but nothing will be deleted), although there will be far more queries than additions to X.
I am free to choose the data structure representing the elements of X.
Obviously, we could represent X as a std::set or sorted std::vector of std::uint64_t, and I give one algorithm below. But can we do better?
What are good data structures for X and algorithms to do this efficiently? This should be a standard problem but I couldn't find anything.
EDIT: sorry if this is too vague. Obviously, if X were a std::set we could search through all subsets of A, taking time O(2^m log |X|) with m <= N, or all elements of X in time O(|X| log |X|).
Assume that in most cases, the number of B is quite a bit smaller than both 2^m (the number of subsets of A) and |X|. So, we want some kind of algorithm to run in time much less than |X| or 2^m in such cases, ideally in time O(number of B) but that's surely too optimistic. Obviously, O(|X|) cannot be beaten in the worst case.
Obviously some memory overhead for X is expected, and memory is less of a bottleneck than time for me. Using memory roughly 10 * (the memory of X stored as a std::set) is fine. Much more than this is too much. (Asymptotically, anything more than O(|X|) or O(|X| log |X|) memory is probably too much).
Obviously, the use of C++ is not essential: the algorithms/data structures are the important things here.
In the case that X is fixed, maybe Hasse diagrams could work.
It looks like Hasse diagrams would be quite time-consuming to construct each time X grows. (But still maybe worth a try if nothing else comes up). EDIT: maybe not so slow to update, so better than I thought.
The below is just my idea so far; maybe something better can be found?
FINAL edit: since it's closed, probably fairly - the "duplicate" question is pretty close - I won't bother with any further edits. I will probably do the below, but using a probabilistic skip list structure instead of a std::set, and augmented with skip distances (so you can quickly calculate how many X elements remain in an interval, and thus reduce the number of search intervals, by switching to linear search when the intersection gets small). This is similar to Order Statistic Trees given in this question, but skip lists are a lot easier to reimplement than std::set (especially as I don't need deletions).
Represent X as a std::set or sorted std::vector of 64-bit unsigned integers std::uint64_t, using the ordinary numerical order, and do recursive searches within smaller and smaller intervals.
E.g., my query element is A = 10011010. Subsets of A containing the first bit lie in the inclusive interval [10000000, 10011010].
Subsets of A containing the second bit but not the first lie in the interval [00010000, 00011010].
Those with the third but not the second bit are in [00001000, 00001010].
Those with the fourth but not the third bit are in [00000010, 00000010].
Now, within the first interval [10000000, 10011010] you could make two subintervals to search, based on the second bit: [10000000, 10001010] and [10010000, 10011010].
Thus you can break it down recursively in this manner. The total length of search intervals is getting smaller all the time, so this is surely going to be better asymptotically than a trivial linear search through all of X.
E.g., if X = {00000010, 00001000, 00110111, 10011100} then only the first, third, fourth depth-1 intervals would have nonempty intersection with X. The final returned result would be [00000010, 00001000].
Of course this is unbalanced if the X elements are distributed fairly uniformly. We might want the search intervals to have roughly equal width at each depth, and they don't; above, the sizes of the four depth-1 search intervals are, I think, 27, 11, 3, 1, and for larger N the discrepancies could be much bigger.
If there are k bits in the query set A, then you'll have to construct k initial search intervals at depth 1 (searching on ONE bit), then up to 2k search intervals at depth 2, 4k at depth 3, etc.
If I've got it right, since log |X| = O(N) the number of search intervals is O(k + 2k + 4k + ... + 2^n . k) = O(k^2) = O(N^2), where 2^n = O(k), and each one takes O(N) time to construct (actually a bit less since it's the log of a smaller number, but the log doesn't increase much), so it seems like this is an O(N^3) algorithm to construct the search intervals.
Of course the full algorithm is not O(N^3), because each interval may contain many elements, so listing them all cannot be better than O(2^N) in general, but let's ignore this and assume that there are not enough elements of X to overwhelm the O(N^3) estimate.
Another issue is that std::map cannot tell you how many elements lie within an interval (unlike a sorted std::vector) so you don't know when to break off the partitioning and search through all remaining X elements in the interval. Of course, you have an upper bound on the number of X elements (the size of the full interval) but it may be quite poor.
EDIT: the answer to another question shows how to have a std::set-like structure which also quickly gives you the number of elements in a range, which obviously could be adapted to std::map-like structures. This would work well here for pruning (although annoying that, for C++, you'd have to reimplement most of std::map!)