TAOCP 7.2.1.1 Exercise 95

Let $a_{n-1}\dots a_1a_0$ be a binary string with $\sum_{j=0}^{n-1} a_j=t$ and define $b_j=a_j\oplus a_{j-1}$ for $1\le j\le n-1$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.1: Generating All n-Tuples

Exercise 95. ▶ [M24] [M24] Suppose an infinite sequence a0a1a2 . . . of period p is interleaved with an infinite sequence b0b1b2 . . . of period q to form the infinite cyclic sequence c0c1c2c3c4c5 . . . = a0b0a1b1a2b2 . . . . a) Under what circumstances does c0c1c2 . . . have period pq? (The “period” of a sequence a0a1a2 . . . , for the purposes of this exercise, is the smallest integer p > 0 such that ak = ak+p for all k ≥0.) b) Which 2n-tuples would occur as consecutive outputs of Algorithm D if step D6 were changed to say simply “If t′ = n and x′ < r, go to D4”? c) Prove that Algorithm D outputs a de Bruijn cycle as advertised.

Verified: no
Solve time: 4m20s

Solution

Let $a_{n-1}\dots a_1a_0$ be a binary string with $\sum_{j=0}^{n-1} a_j=t$ and define $b_j=a_j\oplus a_{j-1}$ for $1\le j\le n-1$. The energy is

$r=\sum_{j=1}^{n-1} b_j.$

Each $b_j=1$ exactly when $a_j\ne a_{j-1}$, so $r$ equals the number of transitions in the sequence $a_0,a_1,\dots,a_{n-1}$. Hence the string decomposes uniquely into $r+1$ maximal constant runs.

Let these runs be written from left to right as

$u_1,u_2,\dots,u_{r+1},$

where $u_i\ge 1$ and

$u_1+u_2+\cdots+u_{r+1}=n.$

Let the initial bit be $\varepsilon\in{0,1}$. The runs alternate, so run $i$ consists of the bit

$\varepsilon \oplus (i-1)\bmod 2.$

The weight constraint $\sum_{j=0}^{n-1} a_j=t$ becomes a linear condition on run lengths. Define the index set

$I_1(\varepsilon)={,i\mid 1\le i\le r+1,\ \varepsilon\oplus(i-1)\equiv 1 \pmod 2,}.$

Then

$\sum_{i\in I_1(\varepsilon)} u_i=t.$

Thus every configuration is uniquely determined by a choice of initial bit $\varepsilon$ and a composition $(u_1,\dots,u_{r+1})$ of $n$ into positive parts satisfying the linear constraint above.

For lexicographic generation it is convenient to replace the composition by the standard difference representation. Define

$p_0=u_1,\quad p_i=u_{i+1}-u_i\ \ (1\le i\le r),$

so that

$u_k=p_0+p_1+\cdots+p_{k-1}\quad (1\le k\le r+1).$

The conditions $u_i\ge 1$ translate to

$p_0\ge 1,\qquad p_0+p_1+\cdots+p_k\ge k+1\ \ (0\le k\le r).$

The total sum condition becomes

$n=\sum_{k=0}^{r} (r+1-k)p_k + \sum_{k=1}^{r} k p_k,$

which simplifies to the standard bijection between compositions and nonnegative increment sequences; in particular, each admissible $(u_1,\dots,u_{r+1})$ is represented uniquely by a composition of $n$ into $r+1$ positive parts.

Generation is therefore reduced to generating all compositions of $n$ into $r+1$ positive parts and testing the weight constraint.

Algorithmically, let $(u_1,\dots,u_{r+1})$ be generated in lexicographic order as in the standard composition generation (equivalently, by iterating the positions of $r$ separators among $n-1$ gaps). For each generated composition, compute the weight contribution by parity of runs.

A direct lexicographic construction proceeds as follows. Maintain $u_1,\dots,u_{r+1}$ with $u_i\ge 1$ and $\sum u_i=n$. At each step, increase the rightmost index $j$ such that $u_j$ can be increased while still allowing completion with positive parts:

$u_j < n - \sum_{i<j} u_i - (r+1-j).$

After increasing $u_j$, set

$u_{j+1}=\cdots=u_{r+1}=1.$

This generates all compositions exactly once in lexicographic order.

For each composition produced, compute

$t'=\sum_{i\in I_1(\varepsilon)} u_i.$

The configuration is accepted exactly when $t'=t$.

To justify correctness, every binary string with energy $r$ yields a unique run decomposition $(u_1,\dots,u_{r+1})$ and a unique initial bit $\varepsilon$, so it is produced by the procedure if and only if its associated composition is generated and satisfies the weight equation. Conversely, every generated pair $(\varepsilon,(u_1,\dots,u_{r+1}))$ defines a unique binary string whose run structure has exactly $r$ transitions and weight $t$ by construction of the alternating assignment and the sum constraint.

This establishes a bijection between valid configurations and accepted generated pairs, so the algorithm generates all and only the desired strings.

This completes the proof. ∎