Section 7.2.2.1: Dancing Links

Exercise 95. ▶ [20] [20] Given $0 \le p \le q \le n$, explain how to use color controls and Algorithm C to find all cycles $(x_0 x_1 \ldots x_{m-1})$ of 0s and 1s, where $m = \sum_{k=0}^{1} \binom{n}{k}$, with the property that the $m$ binary vectors ${x_0 x_1 \ldots x_{n-1}, x_1 x_2 \ldots x_n, \ldots, x_{m-1} x_0 \ldots x_{n-2}}$ are distinct and have weight between $p$ and $q$. (In other words, all $n$-bit binary vectors $y = y_1 \ldots y_n$ with $p \le \nu y \le q$ occur exactly once in the cycle.) We studied the special case of de Bruijn cycles, for which $p = 0$ and $q = n$, in Section 7.2.1.1.)

For example, when $n = 7$, $p = 0$, and $q = 3$, the cycle

$$\langle 00000001000011000010100110010010000101000110010001100101110001111 \rangle$$

exhibits all binary 7-tuples with a majority of 0s. When $n = 7$, $p = 4$, the cycle

$$\langle 00001110001100110101010101010110110011001110100011100101111 \rangle$$

shows all 7-tuples $x_1 \ldots x_7$ whose weight $\nu(x_1 \ldots x_7) \ge 4$, so its length is $\binom{7}{4}+\binom{7}{5}+\binom{7}{6}+\binom{7}{7} = 35+21+7+1 = 64$. How long does it take for Algorithm C to find them?

Verified: no
Solve time: 1m37s

---

Solution

Let

$$ S={y_1\ldots y_n: y_i\in{0,1},\ p\leq \nu(y_1\ldots y_n)\leq q}. $$

The required cycle has one occurrence of every member of $S$ as a consecutive block of length $n$. The number of required blocks is

$$ m=|S|=\sum_{k=p}^{q}\binom nk . $$

A candidate cycle of length $m$ can be viewed as a cyclic sequence of bits. Its successive length-$n$ windows must move through the elements of $S$ exactly once. The overlap between two windows is determined by deleting the first bit and appending a new bit. Hence the problem is a restricted de Bruijn cycle problem.

Construct the directed graph whose vertices are the elements of $S$. There is an arc

$$ y_1y_2\ldots y_n\longrightarrow y_2y_3\ldots y_nz $$

precisely when

$$ y_2y_3\ldots y_nz\in S $$

and $z\in{0,1}$. A required cycle is equivalent to an ordering of all vertices of this graph in which consecutive vertices are joined by arcs. Therefore Algorithm C can be applied to this graph in exactly the same way that it is applied for ordinary de Bruijn cycles, except that vertices whose weights are not in the interval $[p,q]$ are removed before the search begins.

The color controls provide the necessary restriction. Give each position in the cyclic word a color according to the weight of the length-$n$ block beginning at that position. The admissible colors are

$$ p,p+1,\ldots,q . $$

During Algorithm C, a partial cycle is rejected whenever its current length-$n$ block receives a color outside this range. Equivalently, the color control deletes all transitions that would create a forbidden block. Every completed cycle therefore contains only blocks whose weights satisfy

$$ p\leq \nu(y)\leq q . $$

Conversely, suppose that

$$ (x_0x_1\ldots x_{m-1}) $$

has the required property. Every cyclic window

$$ x_i x_{i+1}\ldots x_{i+n-1} $$

has weight between $p$ and $q$, so every transition used by this cycle remains after the color controls have removed the forbidden transitions. The cycle is therefore one of the cycles explored by Algorithm C. Thus the restriction does not remove any valid answer.

The length of the cycle is forced by the number of admissible windows. There are

$$ \binom n0+\binom n1+\cdots+\binom nn=2^n $$

possible binary vectors of length $n$, and the restriction retains exactly

$$ \sum_{k=p}^{q}\binom nk $$

of them. Hence every successful cycle has length

$$ m=\sum_{k=p}^{q}\binom nk . $$

For the example $n=7$, $p=0$, and $q=3$, the number of admissible blocks is

$$ \binom70+\binom71+\binom72+\binom73

1+7+21+35

$$

For $n=7$, $p=4$, and $q=7$, the number of admissible blocks is

$$ \binom74+\binom75+\binom76+\binom77

35+21+7+1

$$

Algorithm C searches the remaining branching space after the color controls have removed every partial choice containing an inadmissible block. Its running time is proportional to the number of partial cycles that survive these tests, because each surviving extension is examined once and each failure is detected when a color control becomes violated. The two examples therefore take the time required by Algorithm C to enumerate all admissible cycles among the corresponding restricted transition graphs, rather than the time required for the full $2^n$-vertex de Bruijn search.

Thus the required cycles are obtained by running Algorithm C with the ordinary de Bruijn transition rule together with color controls that allow exactly the weights $p,p+1,\ldots,q$. This produces precisely all binary cycles satisfying the stated condition. ∎