# Iterating over a union of sets denoted by bitmasks

Consider the set $$\mathbb{B}^n$$ of all $$n$$-digit binary numbers. Let us define a bitmask as a tuple $$M=(m_0,\ldots,m_{n-1})$$, where $$m_i\in \{0,1,*\}$$. Such bitmask denotes a set $$S \subset \mathbb{B}^n$$ containing all numbers with digits $$b_0...b_{n-1}$$ such that $$\forall i \in [0, n-1]: m_i \neq * \Rightarrow b_i=m_i$$.

For example the bitmask 1*0* would denote the set $$\{1000, 1001, 1100, 1101\}$$.

Given a set of $$k$$ such bitmasks $$\{M_i: i \in [0, k-1]\}$$, how to efficiently iterate over the union of the corresponding sets of binary numbers in lexicographical order? By efficiently I mean doing some pre-processing in polynomial time and then computing each next number in $$O(n)$$ amortized time and also using a polynomial amount of memory.

• What dependence on $k$ are you aiming at? – Yuval Filmus Jun 14 '19 at 14:05
• Ideally $k$ should only affect preprocessing time (which should be a polynomial of $k$ and $n$). – Mikhail Maltsev Jun 14 '19 at 14:10
• Let us call 0 and 1 bits. Call $*$ a mask. There are ${n\choose{n/2}}$ possible values of $M$ whose number of bits is $n/2$. Each set of such $M$ will correspond to a different union of binary numbers. So we could have $2^{n\choose{n/2}}$ different cases. The magnitude of this double exponentiation indicates it might be difficult or even impossible to find an efficient algorithm. – John L. Jun 17 '19 at 2:35