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.

  • $\begingroup$ What dependence on $k$ are you aiming at? $\endgroup$ – Yuval Filmus Jun 14 '19 at 14:05
  • $\begingroup$ Ideally $k$ should only affect preprocessing time (which should be a polynomial of $k$ and $n$). $\endgroup$ – Mikhail Maltsev Jun 14 '19 at 14:10
  • $\begingroup$ 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. $\endgroup$ – John L. Jun 17 '19 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.