An efficient generalized algorithm to obtain an arbitrary element of a lexicographically ordered tuple of all balanced $l$-bit binary sequences

Question

Assuming that $l>1$ is even, an $l$-bit binary sequence $b$ is balanced if and only if the number of zeroes in $b$ is equal to $l/2$.

Let $T_l$ denote a lexicographically ordered tuple of all balanced $l$-bit binary sequences: $$T_l = (b_1, b_2, \ldots, b_{k_l-1}, b_{k_l}),$$ where $k_l = \binom{l}{l/2}$. For example, $$\begin{array}{l} T_4 = (\text{0011},\\ \text{0101},\\ \text{0110},\\ \text{1001},\\ \text{1010},\\ \text{1100}). \end{array}$$

Question: given an arbitrary pair of numbers $(l, i)$ where $i \leq k_l$, is there an efficient algorithm to obtain an $i$-th element of $T_l$?

Answer 1

The first one appears at the $(\ell-k)$th position, where $k$ is the smallest number such that ${k\choose \ell/2}\geq i$. The second appears at the $(\ell-k')$th position where $k'$ is the least number satisfying ${k-1\choose \ell/2}+{k'\choose \ell/2-1}\geq i$. Similarly you find the other bits.

Answer 2

If the efficiency is very important for you, you should consider if you really need lexicographic order. Other orders have slightly faster unranking. For example, I like this one for subsets of size $k$.

The rank of $b_1<b_2<\cdots<b_k$ where $b_1\ge 1$, is $$ \binom{b_1-1}{1} + \binom{b_2-1}{2} + \cdots + \binom{b_k-1}{k}.$$

The first rank is 0. You need $\binom{a}{b}=0$ for $b>a$. Compute all the necessary binomial coefficients in advance. A cute thing about this is that the size of the superset is not needed, since the subsets are in order of their largest element.

For $k=3$, the order is 123, 124, 134, 234, 125, 135, 235, 145, 245, 345, ...

Answer 3

Comment to the question suggested the keyword “unranking”. Such algorithms can be found, for example, in the Section 3.2 of the paper “Lexicographic unranking of combinations revisited” [Antoine Genitrini, Martin Pépin; DOI: 10.3390/a14030097].

These algorithms output a tuple of numbers (given $i, l, l/2$). The only thing left is convert this tuple to a binary sequence. For example, the following code in SageMath:

import sage.combinat.combination as combination
print(combination.from_rank(0,4,2))
print(combination.from_rank(1,4,2))
print(combination.from_rank(2,4,2))
print(combination.from_rank(3,4,2))
print(combination.from_rank(4,4,2))
print(combination.from_rank(5,4,2))  

outputs

(0, 1)
(0, 2)
(0, 3)
(1, 2)
(1, 3)
(2, 3),

which are lists of indexes of zeros in the corresponding element of $T_4$.

The link to the code of the unranking algorithm of the from_rank(r, n, k) function can be found in footnote 7 on page 12 of the paper.