TAOCP 7.2.2.1 Exercise 223

Exercise 223. [20] Implement the output phase of Algorithm P (step P10).

Verified: no
Solve time: 1m57s

Solution

Let $S$ denote the stack of options accumulated in step P7. Each element of $S$ is a pointer to a node belonging to an option, and each option is represented in memory as a contiguous sequence of nodes separated by spacer nodes, characterized by $\text{TOP}(x) \le 0$.

The output phase must enumerate exactly the options stored in $S$ and, for each such option, print the corresponding set of items. Each item of an option is identified by a node $x$ with $\text{TOP}(x) = i > 0$, and the printed name is $\text{NAME}(i)$.

The required traversal for a single option proceeds inside its sequential block of memory. If $p$ is a node belonging to the option, then the option is obtained by scanning forward in memory order starting at $p$ until a spacer node is reached. That is, letting $q \leftarrow p$, we repeatedly increment $q \leftarrow q+1$ while $\text{TOP}(q) > 0$, since spacer nodes are exactly those with $\text{TOP}(q) \le 0$ and they delimit option boundaries by construction in (11).

The output phase is therefore implemented by repeatedly removing options from $S$ and printing their item sets. While $S \ne \emptyset$, let $p$ be the top element of $S$ and delete it from $S$. Starting at $q \leftarrow p$, the nodes of the option are visited in memory order. For each such node $q$ with $\text{TOP}(q) = i > 0$, the symbol $\text{NAME}(i)$ is output. The scan terminates when a spacer is encountered, that is when $\text{TOP}(q) \le 0$, since at that point the next memory positions no longer belong to the same option.

Each iteration over $S$ outputs exactly one option, because $S$ contains exactly the options selected in the partial solution and no other nodes are inserted into $S$ during step P10. The sequential scan within each option visits each node exactly once, since option nodes occur in contiguous memory blocks separated by spacers, and no node in such a block has $\text{TOP}(x) \le 0$ except the terminating spacer.

The procedure thus outputs the complete solution as a disjoint family of options covering all items exactly once.

This completes the implementation of step P10. ∎