TAOCP 7.2.1.1 Exercise 99
Let $N = 2^n$ and let $f_n(0), f_n(1), \ldots, f_n(N-1)$ be the cycle from Exercise 97, viewed cyclically modulo $N$.
Section 7.2.1.1: Generating All n-Tuples
Exercise 99. ▶ [M23] [M23] Exploit the technology of the previous exercises to design an efficient algorithm that locates any given n-bit string in the cycle (fn(0)fn(1) . . . fn(2n−1)).
Verified: no
Solve time: 2m31s
Solution
Let $N = 2^n$ and let $f_n(0), f_n(1), \ldots, f_n(N-1)$ be the cycle from Exercise 97, viewed cyclically modulo $N$. From Exercise 97(a) and (b), there exists an index $j_n$ such that
$$ f_n(k) = 0 \quad (0 \le k < j_n), \qquad f_n(k) = 1 \quad (j_n \le k < j_n + n), $$
with all indices taken modulo $N$. Hence the sequence consists of a single cyclic block of $n$ consecutive $1$-bits and $N-n$ zero bits.
Define the prefix sum
$$ \Sigma f_n(k) = \sum_{t=0}^{k-1} f_n(t), \qquad \Sigma f_n(0)=0. $$
From Exercise 98, $\Sigma f_n(k)$ can be evaluated in constant time, since it differs from a piecewise linear function with a single jump of height $n$ at $j_n$.
Let the input $n$-bit string be
$$ x = x_0 x_1 \cdots x_{n-1}. $$
Write
$$ |x|1 = \sum{i=0}^{n-1} x_i, $$
and decompose $x$ uniquely as a cyclic binary string into maximal runs of consecutive $1$-bits in the linear representation. Since $x$ has length $n$, there are three cases: either $|x|_1 = 0$, or $|x|_1 = n$, or $0 < |x|_1 < n$, in which case $x$ has exactly one run of consecutive $1$-bits of length $|x|_1$ in its linear form, possibly with wrap-around.
For any starting position $k$, consider the window
$$ W_k = {k, k+1, \ldots, k+n-1} \pmod N. $$
The pattern in the window is completely determined by the intersection of $W_k$ with the interval
$$ I = {j_n, j_n+1, \ldots, j_n+n-1} \pmod N. $$
Since $I$ is a single interval of length $n$ on the cycle of length $N$, the intersection $W_k \cap I$ is also a single cyclic interval (possibly empty or the whole window). Therefore the binary word $(f_n(k), \ldots, f_n(k+n-1))$ has the form $0^a 1^b 0^c$ in cyclic order, where $b = |W_k \cap I|$.
Hence the number of $1$-bits in the window satisfies
$$ b = \Sigma f_n(k+n) - \Sigma f_n(k). $$
The string $x$ fixes $b = |x|_1$, and also fixes whether the block of $1$-bits in $x$ touches the left or right boundary of the window. If $x$ begins with $1$, then the window must start inside or immediately before the interval $I$; if $x$ ends with $1$, then the window must end inside or immediately after $I$. These two boundary conditions determine the alignment uniquely up to at most two candidates for $k$.
To extract these candidates, write $x$ in linear form starting at position $0$ and let $a$ be the number of leading zeros, and $c$ the number of trailing zeros, so that
$$ x = 0^a 1^b 0^c \quad \text{with } a+b+c=n \text{ in cyclic sense}. $$
Then any occurrence of $x$ must satisfy one of the two alignment equations modulo $N$:
$$ k \equiv j_n - a \pmod N, $$
corresponding to the case where the $1$-block of the window begins exactly at the start of $I$, and
$$ k \equiv j_n + n - b \pmod N, $$
corresponding to the case where the $1$-block of the window ends exactly at the end of $I$.
Each candidate $k$ produces a window whose intersection size with $I$ equals $b$, and the cyclic placement of the single interval $I$ forces the pattern inside the window to be fully determined by this intersection, so at most two positions can match $x$.
The algorithm evaluates $\Sigma f_n(k)$ and $f_n(k)$ in constant time from Exercise 98, computes $a$ and $b$ from $x$, forms the at most two candidate indices above, and verifies equality by direct evaluation of $f_n$ on $n$ positions of the window.
This completes the construction of an efficient locating procedure for any given $n$-bit string in the cycle. ∎