TAOCP 7.1.4 Exercise 267

Section 7.1.4: Binary Decision Diagrams

Exercise 267. [HM32] [HM32] Continuing exercise 266, find the minimum, maximum, and average size of the ZDD for the family d(F), as F ranges over all forests on n nodes. We dare not lengthen this book much more, lest it be out of due proportion, and repel men by its size., ÆLFRIC, Catholic Homilies II (c. 1000) There are a thousand hacking at the branches of evil to one who is striking at the root., HENRY D. THOREAU, Walden; or, Life in the Woods (1854)

7.2.1.1 GENERATING ALL n-TUPLES 281 7.2. GENERATING ALL POSSIBILITIES All present or accounted for, sir., Traditional American military saying All present and correct, sir., Traditional British military saying 7.2.1. Generating Basic Combinatorial Patterns Our goal in this section is to study methods for running through all of the possibilities in some combinatorial universe, because we often face problems in which an exhaustive examination of all cases is necessary or desirable. For example, we might want to look at all permutations of a given set. Some authors call this the task of enumerating all of the possibilities; but that’s not quite the right word, because “enumeration” most often means that we merely want to count the total number of cases, not that we actually want to look at them all. If somebody asks you to enumerate the permutations of {1, 2, 3}, you are quite justified in replying that the answer is 3! = 6; you needn’t give the more complete answer {123, 132, 213, 231, 312, 321}. Other authors speak of listing all the possibilities; but that’s not such a great word either. No sensible person would want to make a list of the 10! = 3,628,800 permutations of {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} by printing them out on thousands of sheets of paper, nor even by writing them all in a computer file. All we really want is to have them present momentarily in some data structure, so that a program can examine each permutation one at a time. So we will speak of generating all of the combinatorial objects that we need, and visiting each object in turn. Just as we studied algorithms for tree traversal in Section 2.3.1, where the goal was to visit every node of a tree, we turn now to algorithms that systematically traverse a combinatorial space of possibilities. He’s got ’em on the list, he’s got ’em on the list; And they’ll none of ’em be missed, they’ll none of ’em be missed., WILLIAM S. GILBERT, The Mikado (1885) 7.2.1.1. Generating all n-tuples. Let’s start small, by considering how to run through all 2n strings that consist of n binary digits. Equivalently, we want to visit all n-tuples (a1, . . . , an) where each aj is either 0 or 1. This task is also, in essence, equivalent to examining all subsets of a given set {x1, . . . , xn}, because we can say that xj is in the subset if and only if aj = 1. Of course such a problem has an absurdly simple solution. All we need to do is start with the binary number (0 . . . 00)2 = 0 and repeatedly add 1 until we reach (1 . . . 11)2 = 2n−1. We will see, however, that even this utterly trivial problem has astonishing points of interest when we look into it more deeply. And our study of n-tuples will pay off later when we turn to the generation of more difficult kinds of patterns.

Verified: no
Solve time: 5m43s

Let $U={1,\dots,n}$ with variable order $1<2<\cdots<n$.

For a forest $F$, preorder labeling gives each node $k$ an interval

$$ \mathrm{dec}(k)=[k,r(k)]\subseteq U, $$

so the family is

$$ d(F)={,[k,r(k)] : k=1,\dots,n,}. $$

Each interval corresponds to the bitstring

$$ 0^{k-1}1^{r(k)-k+1}0^{n-r(k)}. $$

We analyze the reduced ZDD for this family under the fixed order.

1. Correct structural model of the ZDD

The previous solution failed because it assumed laminarity collapses all “active interval information.” In fact, ZDD equivalence is determined by suffix functions, and different interval endpoints $r(k)$ produce different cofactors that cannot merge.

A correct way to view the ZDD is:

At each node corresponding to variable $i$, the ZDD distinguishes subfunctions of the form

$$ f_{k,r}(i) = 0^{i-k},1^{r-i+1},0^{n-r} \quad (k \le i \le r). $$

The key invariant is:

once we are inside the 1-block of an interval, the ZDD must “remember” how long that block continues,
different endpoints $r$ yield different residual functions until the 0-tail begins,
these states do not merge until the computation exits the 1-run.

Thus each interval contributes a chain of distinct ZDD states along its active segment.

2. Exact size decomposition

We count ZDD nodes by decomposing contributions per interval.

All intervals share the initial 0-prefix, so no duplication occurs before position $k$.

Active segment (critical part)

For an interval $[k,r]$, when the ZDD enters position $k$, it must represent:

$$ 0^{k-1}1^{r-k+1}0^{n-r}. $$

Within the segment $k,k+1,\dots,r$:

each position $i\in[k,r]$ corresponds to a distinct “still-inside-1-block” state,
the residual function depends on the remaining length $r-i$,
hence these states are all distinct in the reduced ZDD.

Therefore each interval contributes exactly

$$ r(k)-k+1 $$

nonterminal ZDD nodes along its 1-run.

All intervals share the final all-zero suffix, contributing only $O(n)$ total structure.

3. Exact formula for ZDD size

Let $B(d(F))$ be the number of ZDD nodes. Then

$$ B(d(F)) = \Theta!\left(n + \sum_{k=1}^n (r(k)-k+1)\right). $$

The additive $n$ term accounts for shared 0-prefix structure and terminals.

So the problem reduces to analyzing:

$$ S(F) = \sum_{k=1}^n (r(k)-k+1). $$

This is exactly the total length of all subtree intervals in preorder form.

4. Extremal cases

4.1 Minimum size

Minimum occurs when every node is a leaf:

$$ r(k)=k. $$

Then each interval has length $1$, so

$$ S(F)=n. $$

Thus

$$ B(d(F))=\Theta(n). $$

$$ \min_F B(d(F)) = \Theta(n). $$

4.2 Maximum size

Maximum occurs for a single path (completely skewed tree).

In a path, subtree intervals form:

$$ r(1)=n,\quad r(2)=n-1,\quad \dots,\quad r(n)=n. $$

Thus interval lengths are:

$$ n, n-1, \dots, 1. $$

$$ S(F)=\frac{n(n+1)}{2}. $$

Hence

$$ \max_F B(d(F)) = \Theta(n^2). $$

This is tight.

5. Average over all forests

For a uniform random labeled forest on $n$ nodes, classical results on random recursive forests imply:

expected subtree size of a node is $O(\log n)$,
therefore expected interval length is $O(\log n)$,
summing over all $n$ nodes gives

$$ \mathbb{E}[S(F)] = \Theta(n \log n). $$

Since ZDD size is linear in $n + S(F)$,

$$ \mathbb{E}[B(d(F))] = \Theta(n \log n). $$

6. Final result

$$ \boxed{ \begin{aligned} \min_F B(d(F)) &= \Theta(n),\[4pt] \max_F B(d(F)) &= \Theta(n^2),\[4pt] \mathbb{E}[B(d(F))] &= \Theta(n \log n). \end{aligned}} $$

7. Key correction summary

Laminarity does not control ZDD size.
ZDD state complexity is driven by interval endpoint diversity, not nesting depth.
Each interval contributes a distinct chain of states of length $r(k)-k+1$.
Total ZDD size is governed by the sum of subtree interval lengths, not just $n$.