TAOCP 7.2.1.5 Exercise 47

Let $\varpi_n$ denote the Bell number (the number of partitions of $\{1,2,\ldots,n\}$), which equals the number of restricted growth strings $a_1a_2\ldots a_n$ satisfying $a_1=0$ and $a_{j+1}\le 1+\ma...

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.5: Generating All Set Partitions

Exercise 47. [M21] Analyze the running time of Algorithm H.

Verified: no
Solve time: 8m07s

Solution

Let $\varpi_n$ denote the Bell number (the number of partitions of ${1,2,\ldots,n}$), which equals the number of restricted growth strings $a_1a_2\ldots a_n$ satisfying $a_1=0$ and $a_{j+1}\le 1+\max(a_1,\ldots,a_j)$ for $1\le j<n$. Algorithm H generates all these strings in lexicographic order.
We analyze the total number of executions of each step during the complete generation.

1. Visits (step H2)

Every restricted growth string is visited exactly once, so step H2 is executed $\varpi_n$ times.

2. Calls to H4

Step H4 is entered precisely when $a_n = m$, where $m = 1+\max(a_1,\ldots,a_{n-1})$. For a fixed prefix $P = a_1\ldots a_{n-1}$ (which is itself a restricted growth string of length $n-1$), the algorithm runs through $a_n = 0,1,\ldots,m$; the last value $a_n=m$ triggers H4. Since every restricted growth string of length $n-1$ occurs exactly once as a prefix during the generation, the number of entries into H4 equals the number of such prefixes, namely $\varpi_{n-1}$.

3. Iterations of the H4 while loop

During a call to H4 the algorithm sets $j=n-1$ and then repeatedly decrements $j$ while $a_j = b_j$, where $b_j = 1+\max(a_1,\ldots,a_{j-1})$. The condition $a_j = b_j$ means that $a_j$ is strictly larger than all preceding elements, i.e. $j$ is the smallest element of its block. The number of decrements in this call is exactly the number of consecutive positions at the end of the prefix $P = a_1\ldots a_{n-1}$ that satisfy $a_j = b_j$; call this the record‑suffix length of $P$.

Let $R(k)$ be the sum of the record‑suffix lengths over all restricted growth strings of length $k$. We have $R(1)=0$ (the single string $0$ has no record at the end). For $k\ge 2$, every string of length $k$ is obtained from a string $P$ of length $k-1$ (with maximum $M$) by appending a value $a_k \in {0,1,\ldots,M+1}$. If $a_k \le M$ then $a_k \neq b_k$, so the record‑suffix length is $0$. If $a_k = M+1$ then $a_k = b_k$, and the record‑suffix length becomes $r(P)+1$, where $r(P)$ is the record‑suffix length of $P$. Summing over all $\varpi_{k-1}$ prefixes gives $$ R(k) = \sum_P \bigl(r(P)+1\bigr) = R(k-1) + \varpi_{k-1}. $$ Solving this recurrence yields $$ R(k) = \varpi_1 + \varpi_2 + \cdots + \varpi_{k-1} \qquad (k\ge 2). $$ The total number of executions of the statement “$j \leftarrow j-1$” in H4 is therefore $$ D(n) = R(n-1) = \varpi_1 + \varpi_2 + \cdots + \varpi_{n-2}. $$

4. Iterations of the H6 while loop

When H4 finishes with a value $j = j_{\text{found}} > 1$, step H5 increments $a_j$ and step H6 is entered. In H6 the loop “while $j < n$” sets $a_j \leftarrow 0$, $b_j \leftarrow m$, $j \leftarrow j+1$ for $j = j_{\text{found}}+1,\ldots,n-1$; it therefore iterates exactly $n-1 - j_{\text{found}}$ times. In the corresponding H4 call the while loop also performed exactly $n-1 - j_{\text{found}}$ decrements. Thus, for every H4 call that leads to H6, the number of H6 while‑iterations equals the number of H4 decrements.

The last H4 call occurs after the final partition $0,1,2,\ldots,(n-1)$ is visited. Its prefix is $0,1,\ldots,(n-2)$, in which $a_j = b_j$ holds for all $j=2,\ldots,n-1$. Hence the final H4 call performs $n-2$ decrements and then terminates in H5 (with $j=1$), without entering H6. Consequently the total number of H6 while‑iterations is $$ E(n) = D(n) - (n-2) = \varpi_1 + \varpi_2 + \cdots + \varpi_{n-2} - (n-2). $$

5. Counts of the remaining steps

  • H3 (increase $a_n$): executed once for every visit except those that go to H4. Number of H3 executions $= \varpi_n - \varpi_{n-1}$.
  • H5: executed once per H4 call, i.e. $\varpi_{n-1}$ times.
  • H6 (entry): executed for all H4 calls except the last one, i.e. $\varpi_{n-1}-1$ times. Each entry also performs the assignments $m \leftarrow b_j + [a_j = b_j]$, $j \leftarrow j+1$, and finally $a_n \leftarrow 0$.

6. Overall running time

All step counts are expressed in terms of Bell numbers. For $n\ge 4$ we have $\varpi_{n-1} < \varpi_n$ and $$ \varpi_1 + \varpi_2 + \cdots + \varpi_{n-2} < \varpi_n, $$ because Bell numbers grow rapidly ($\varpi_n/\varpi_{n-1} \sim n/\ln n \to \infty$). Hence every count above is bounded by a constant multiple of $\varpi_n$. The total number of elementary operations performed by Algorithm H is therefore $O(\varpi_n)$, which means the amortized time per partition is $O(1)$.

Moreover, the fraction of partitions that require a non‑trivial H4 loop is $\varpi_{n-1}/\varpi_n \to 0$, and the average length of the H4 loop when it is executed is $D(n)/\varpi_{n-1} = (\varpi_1+\cdots+\varpi_{n-2})/\varpi_{n-1} < 1$ for $n\ge 4$. Thus steps H4-H6 are “rarely necessary” and their loops are “almost always short,” as stated in the text.

This completes the proof. ∎