TAOCP 7.2.2.1 Exercise 42
The counting algorithm of exercise 40 loses information because each database entry $(s_j,c_j)$ stores only the number of ways to obtain the set $s_j$.
Section 7.2.2.1: Dancing Links
Exercise 42. [M21] [M21] Explain how the method of exercise 40 could be extended to give representations of all solutions, instead of simply counting them.
Verified: yes
Solve time: 1m24s
Solution
The counting algorithm of exercise 40 loses information because each database entry $(s_j,c_j)$ stores only the number of ways to obtain the set $s_j$. To recover all solutions, replace the counter $c_j$ by a representation of the family of partial covers that produce $s_j$.
Let $C_j$ denote the collection of partial covers represented by the database entry $(s_j,C_j)$. Initially there is one empty partial cover:
$N\leftarrow 1,\qquad s_1\leftarrow 0,\qquad C_1\leftarrow{\varnothing},\qquad k\leftarrow 1.$
At step $k$, each current entry represents all choices among the first $k-1$ rows. When row $r_k$ is appended, every partial cover whose represented set is disjoint from $r_k$ can be extended by adding row $k$. Therefore the insertion operation must attach the new row number to every partial cover in the corresponding collection.
The modified algorithm is:
$$ \begin{array}{ll} \textbf{N1.} & \text{Set }N\leftarrow1,\ s_1\leftarrow0,\ C_1\leftarrow{\varnothing},\ k\leftarrow1.\[3pt] \textbf{N2.} & \text{If }k>m,\text{ output all members of }C_j\text{ such that }s_j\mathbin{&}p=p,\ &\text{and terminate.}\[3pt] \textbf{N3.} & \text{Set }t\leftarrow r_k. \text{ For }N\ge j\ge1,\text{ if }s_j\mathbin{&}t=0,\ &\text{insert }(s_j+t,C'_j)\text{ into the database, where}\ & C'_j={X\cup{k}:X\in C_j}.\[3pt] \textbf{N4.} & \text{Set }k\leftarrow k+1\text{ and return to N2.} \end{array} $$
The insertion operation is modified as follows. If $s=s_i$ for some existing entry, replace
$C_i\leftarrow C_i\cup C.$
If no such entry exists, perform
$N\leftarrow N+1,\qquad s_N\leftarrow s,\qquad C_N\leftarrow C.$
The invariant after step $k$ is that, for every database entry $(s_j,C_j)$, the collection $C_j$ contains exactly the subsets of ${1,\ldots,k}$ whose rows have bitwise OR equal to $s_j$. This holds initially because the only subset considered is the empty set, whose represented item set is $0$.
Assume the invariant holds after step $k-1$. A subset $X$ of ${1,\ldots,k}$ either does not contain $k$ or contains $k$. In the first case it was already represented before processing $r_k$. In the second case write
$X=Y\cup{k},$
where $Y$ is a subset of ${1,\ldots,k-1}$. The algorithm considers every database entry containing $Y$. If $s_Y\mathbin{&}r_k=0$, then adding row $k$ gives the new represented set
$s_Y+r_k,$
and the algorithm inserts exactly the corresponding extended cover
$Y\cup{k}.$
If $s_Y\mathbin{&}r_k\ne0$, then the rows of $Y$ together with row $k$ overlap in an item, so $X$ cannot be part of an exact cover and must not be retained. Thus the invariant is preserved.
At termination, $k>m$, so every subset of rows has either been retained or discarded according to whether it represents a disjoint collection of rows. The condition
$s_j\mathbin{&}p=p$
selects precisely those collections covering all primary items. For every such entry, the members of $C_j$ are exactly the solutions, because the invariant says that they are exactly the subsets whose covered items are $s_j$, and the final test requires that every required item is present. Conversely, every exact cover has a represented set containing all primary items, so it appears in one of the output collections.
The improvement from counting to listing solutions therefore requires only replacing each integer counter $c_j$ by the family $C_j$ of row-index sets that produce the same bit vector, together with replacing addition of counts by union of families. The same compression by equal represented sets remains valid because all members of a collection have identical future behavior under the remaining rows.