Exercise 202. [24] [24] What changes are needed to the swap-in-place algorithm of exercise 147, when levels j u ↔ j v are being interchanged in a ZDD base instead of a BDD base?

Verified: no
Solve time: 4m58s

We restart the argument from the actual structure of Knuth’s swap-in-place algorithm (Exercise 147) and then isolate exactly what changes in the ZDD setting.

The key point is that the swap is not a relabeling and not a simple “replace MK.” It is a local two-level reconstruction in which nodes of levels $j_u$ and $j_{u+1}$ are systematically redistributed according to their 0- and 1-edges. In ZDDs, the only additional complication is that nodes may disappear due to zero-suppression, and this disappearance can occur during the recursion, not only at the moment of node creation.

1. What the BDD swap-in-place actually does

Let the current ordered structure have levels

$$ j_u < j_{u+1}. $$

For a node $x$, write

$$ x = (j_k, x_0, x_1). $$

The swap produces a new representation where the relative order of $j_u$ and $j_{u+1}$ is reversed, while all other levels remain unchanged.

Knuth’s algorithm works by a recursive partition of cases depending on whether the root is above, at, or below the swapped band, and within the band it constructs four subproblems corresponding to the combinations of decisions at the two levels:

$$ (j_u, j_{u+1}) \in {0,1}^2. $$

This yields the standard decomposition:

$f_{00}$: both edges low,
$f_{01}$: low then high,
$f_{10}$: high then low,
$f_{11}$: both high.

The swap reconstructs these into two new nodes in the reversed order, with correct interleaving of shared subgraphs.

This two-level expansion is the essential part that the previous solution omitted.

2. ZDD-specific difference

A ZDD node

$$ (j_k, L, H) $$

represents inclusion/exclusion of element $j_k$, with reduction rule:

$$ H = \bot ;\Rightarrow; (j_k, L, H) \equiv L. $$

This rule has two consequences during swap:

Nodes can disappear during recursion, not only at creation time.
The “high branch” being $\bot$ collapses structure, so some of the four BDD subcases merge earlier than in the BDD algorithm.

Crucially, the swap algorithm must therefore apply ZDD reduction immediately after every recursive construction, not as a final step.

3. Correct swap-in-place structure for ZDDs

We define a memoized procedure

$$ \operatorname{SWAP}(x) $$

that swaps levels $j_u \leftrightarrow j_{u+1}$ in the subgraph rooted at $x$.

A unique table is assumed for ZDD nodes, and every construction uses a ZDD-aware MK:

$$ \operatorname{MK}(j_k, L, H) = \begin{cases} L & \text{if } H = \bot,\ \text{unique}(j_k, L, H) & \text{otherwise}. \end{cases} $$

3.1 Base cases

$$ \operatorname{SWAP}(\bot)=\bot,\quad \operatorname{SWAP}(\top)=\top. $$

3.2 Case 1: node above the swapped levels

Let $x = (j_k, x_0, x_1)$ with $k < u$.

The swap does not affect its level, but its children may contain swapped structure:

$$ x_0' = \operatorname{SWAP}(x_0), \quad x_1' = \operatorname{SWAP}(x_1). $$

Return:

$$ \operatorname{MK}(j_k, x_0', x_1'). $$

No structural change occurs at this node.

3.3 Case 2: node below the swapped levels

Let $k > u+1$. The same reasoning applies:

$$ \operatorname{MK}(j_k, \operatorname{SWAP}(x_0), \operatorname{SWAP}(x_1)). $$

Again, no restructuring at the swap boundary is needed.

3.4 Critical case: nodes at the swapped levels

This is where the previous solution failed.

We must explicitly construct the four-way decomposition.

Step 1: normalize subfunctions

Let

$$ x = (j_u, L, H). $$

We first swap children:

$$ L' = \operatorname{SWAP}(L), \quad H' = \operatorname{SWAP}(H). $$

Similarly, whenever we encounter a node at level $j_{u+1}$, we treat it symmetrically.

Step 2: expand one level down to expose $j_{u+1}$

In the swapped structure, any occurrence of level $j_{u+1}$ must be pulled above level $j_u$. Therefore we conceptually expand:

from $j_u$,
then from $j_{u+1}$,

forming four cases:

$$ \begin{aligned} f_{00} &= L'0, \ f{01} &= L'1, \ f{10} &= H'0, \ f{11} &= H'_1, \end{aligned} $$

where $X_0, X_1$ denote the low/high cofactors of $X$ at level $j_{u+1}$.

This step is the missing interleaving structure: the swap is a local product over two decision levels.

Step 3: rebuild in reversed order

After swap, $j_{u+1}$ comes before $j_u$, so we construct:

Node at level $j_{u+1}$:

$$ y = \operatorname{MK}(j_{u+1}, f_{00}, f_{10}) $$

Node at level $j_u$:

$$ \operatorname{MK}(j_u, y, z) $$

where

$$ z = \operatorname{MK}(j_{u+1}, f_{01}, f_{11}) $$

This is the correct interleaving pattern: two ZDD nodes replacing one BDD node, preserving ordering and all paths.

3.5 Symmetric case: node at $j_{u+1}$

If $x = (j_{u+1}, L, H)$, we perform the same construction with roles of $j_u$ and $j_{u+1}$ reversed, producing the same two-node structure in opposite order.

4. Where zero-suppression actually changes the algorithm

The previous solution incorrectly confined zero-suppression to MK. The correct effect is stronger:

If any constructed node has high child $\bot$, it collapses immediately.
This collapse can reduce the two-node structure back into a single node or even propagate upward.

Thus the swap algorithm must treat MK as part of the recursion, not a post-processing step.

However, no change to the case structure is needed. Only this invariant is added:

Every intermediate node is normalized immediately under ZDD reduction before memoization.

This ensures correctness of sharing and prevents distinct recursive states from being stored separately when they are ZDD-equivalent.

5. Why the BDD swap structure is not reused

The previous solution was incorrect in claiming structural identity with the BDD algorithm.

The correct statement is:

The BDD swap uses a 4-way decomposition at the swapped boundary.
The ZDD swap uses the same 4-way decomposition.
The difference is that in ZDDs, some of the four components may collapse due to $H=\bot$, merging cases earlier.

So the structure is not unchanged; it is the same skeleton with possible early contractions.

6. Correctness argument

We prove equivalence and canonicity.

6.1 Preservation of semantics

Every assignment path in the original diagram corresponds to exactly one sequence of decisions through levels $j_u, j_{u+1}$. The swap replaces this pair of decisions with the reversed pair but preserves all four combinations:

$$ (0,0),(0,1),(1,0),(1,1). $$

Thus every path is preserved with identical terminal outcome.

6.2 Effect of zero-suppression

If a high edge at $j_{u+1}$ is $\bot$, then the corresponding case is redundant and collapses to its low child. This matches ZDD semantics exactly and does not remove any distinguishable set element, since “include $j_{u+1}$” in a zero-suppressed node contributes nothing unless it leads to a nonempty extension.

Thus zero-suppression only removes structurally redundant nodes, never semantic distinctions.

6.3 Canonicity

Because:

nodes are created only via ZDD MK,
MK enforces reduction immediately,
memoization ensures uniqueness,

the result is a reduced ordered ZDD under the swapped ordering.

7. Final corrected conclusion

The swap-in-place algorithm for ZDDs requires the same two-level decomposition as in the BDD case at the swapped boundary $j_u \leftrightarrow j_{u+1}$, but it must:

explicitly construct the four cofactors over the two levels,
rebuild two nodes in reversed order,
apply ZDD zero-suppression immediately at every construction step.

The correct modification to Knuth’s algorithm is therefore not merely a change in the MK rule, but the addition of immediate reduction during the recursive swap, which can collapse parts of the intermediate two-node structure.

The final structure is a valid reduced ZDD representing the same set family under the new variable order.

TAOCP 7.1.4 Exercise 202