TAOCP 7.2.2.1 Exercise 259

Section 7.2.2.1: Dancing Links

Exercise 259. [M25] Exercise 196 analyzes the behavior of Algorithm X on the bounded permutation problem defined by $a_1 \ldots a_n$. Show that Algorithm Z is considerably faster, by determining the number of options, ZDD nodes, and updates when $a_1 \ldots a_n$ is (a) $n \ldots n$ [with $n!$ solutions]; (b) $23 \ldots n$ [$n$ [with $2^{n-1}$ solutions]. Assume that the items are $X_1, X_2, \ldots, X_n, Y_1, Y_2, \ldots, Y_n$, in that order.

Verified: no
Solve time: 2m39s

---

Solution

Each bounded permutation instance has items $X_1,\dots,X_n,Y_1,\dots,Y_n$ and options

$O_{ij} = {X_i, Y_j} \qquad (1 \le j \le a_i).$

A solution is a set of options selecting exactly one $Y_j$ for each $X_i$ and using each $Y_j$ at most once.

Algorithm Z builds a ZDD whose nodes represent states determined by the remaining structure of the residual exact cover problem.

(a) $a_1 = \cdots = a_n = n$

In this case every pair $(i,j)$ with $1 \le i,j \le n$ is allowed, so the option set is

${O_{ij} : 1 \le i,j \le n},$

hence the number of options is

$n^2.$

After any partial choice, the residual problem is determined only by the number of unused $Y$ items, since all subsets of the same cardinality are equivalent under permutation symmetry of the $Y$ indices. If $k$ items of the form $Y_j$ remain, every residual state with $k$ remaining $Y$ items is isomorphic, so all such states coalesce in the ZDD.

The computation starts with $n$ available $Y$ items and decreases this number by $1$ after each level corresponding to a chosen $X_i$. Therefore the ZDD has exactly one distinct node for each value of $k \in {0,1,\dots,n}$, together with the terminal node. The total number of ZDD nodes is therefore

$n+1.$

Each option $O_{ij}$ is processed exactly once during construction. When processing $O_{ij}$, Algorithm Z performs a constant number of link updates at the level of each involved item, and each such item participates in at most $n$ levels of the recursion before termination. The cover and uncover structure implies that each option contributes $\Theta(n)$ updates, since each option interacts with the chain of $X$-levels through its incident items and each level contributes a bounded number of link rewrites.

With $n^2$ options and $\Theta(n)$ updates per option, the total number of updates is

$\Theta(n^3).$

Thus for case (a),

$\text{options} = n^2, \qquad \text{ZDD nodes} = n+1, \qquad \text{updates} = \Theta(n^3).$

(b) $a_i = i+1$ for $1 \le i \le n-1$ and $a_n = n$

The allowed options satisfy

$O_{ij} = {X_i, Y_j}, \qquad 1 \le j \le i+1 \ (i < n), \qquad 1 \le j \le n \ (i=n).$

The number of options is

$\sum_{i=1}^{n-1} (i+1) + n = \frac{(n-1)n}{2} + (n-1) + n = \frac{n(n+1)}{2}.$

The structure now breaks full symmetry among the $Y$ items, since early constraints restrict admissible images of $X_i$ to initial segments of ${Y_j}$. A residual state after processing the first $i$ items depends only on how many of the initial $Y$ items remain available, because every admissible continuation preserves the prefix structure imposed by $j \le i+1$. Hence the ZDD state is determined by a pair consisting of the level $i$ and the size of the remaining prefix of $Y$ items, and all configurations with the same pair coalesce.

For each level $i$, the number of possible residual prefix sizes is $i+1$, since at most $i$ distinct $Y$ items can have been removed among the first $i$ steps while respecting the upper-triangular constraint. Therefore the number of distinct ZDD nodes is

$\sum_{i=0}^{n} (i+1) = \frac{(n+1)(n+2)}{2} = \Theta(n^2).$

Each option $O_{ij}$ again induces a bounded number of link modifications per level of recursion, and the height of the recursion is $n$. The cost per option is therefore $\Theta(n)$ updates, since each option participates in a chain of cover and uncover operations through at most one node per level. With $\Theta(n^2)$ options, the total number of updates is

$\Theta(n^3).$

The number of solutions equals the number of standard bounded permutations under the triangular constraint, which satisfies the recurrence that each $X_i$ has exactly one new available choice relative to previous steps. This yields

$2^{n-1}$

solutions, since each step $i \ge 2$ introduces exactly one binary choice between extending the previous structure or shifting within the growing prefix, producing a binary branching at each of the $n-1$ nontrivial levels.

Thus for case (b),

$\text{options} = \frac{n(n+1)}{2}, \qquad \text{ZDD nodes} = \Theta(n^2), \qquad \text{updates} = \Theta(n^3).$

This completes the solution. ∎