TAOCP 7.2.1.4 Exercise 56

Let $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots \ge 0)$ and $\mu = (\mu_1 \ge \mu_2 \ge \cdots \ge 0)$ be partitions of the same integer $n$, and assume $\lambda \preceq \mu$ in the majorization or...

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.2.1.4: Generating All Partitions

Exercise 56. ▶ [M32] [M32] Design an algorithm to generate all partitions α such that λ ⪯α ⪯µ, given partitions λ and µ with λ ⪯µ. Note: Such an algorithm has numerous applications. For example, to generate all partitions that have m parts and no part exceeding l, we can let λ be the smallest such partition, namely ⌈n/m⌉. . . ⌊n/m⌋as in exercise 3, and let µ be the largest, namely ((n−m+1)1m−1) ∧(l⌊n/l⌋(n mod l)). Similarly, according to a well-known theorem of H. G. Landau [Bull. Math. Biophysics 15 (1953), 143–148], the partitions of m 2  such that m 2 ⌊m/2⌋m −1 2 ⌈m/2⌉ ⪯α ⪯(m−1)(m−2) . . . 21 are the possible “score vectors” of a round-robin tournament, namely the partitions a1 . . . am such that the jth strongest player wins aj games.

414 COMBINATORIAL SEARCHING 7.2.1.4

Verified: no
Solve time: 16m20s

Setup

Let $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots \ge 0)$ and $\mu = (\mu_1 \ge \mu_2 \ge \cdots \ge 0)$ be partitions of the same integer $n$, and assume $\lambda \preceq \mu$ in the majorization order of Section 7.2.1.4. A partition $\alpha = (a_1 \ge a_2 \ge \cdots \ge a_m \ge 0)$ of $n$ satisfies $\lambda \preceq \alpha \preceq \mu$ exactly when, for all $k \ge 1$,

$$ \lambda_1 + \cdots + \lambda_k \le a_1 + \cdots + a_k \le \mu_1 + \cdots + \mu_k, $$

with the convention that missing parts are $0$.

Define prefix sums $S_k = a_1 + \cdots + a_k$, and boundary sums

$$ \Lambda_k = \lambda_1 + \cdots + \lambda_k, \qquad M_k = \mu_1 + \cdots + \mu_k. $$

The task is to generate all partitions $\alpha$ of $n$ such that $\Lambda_k \le S_k \le M_k$ for every $k$, while maintaining $a_1 \ge a_2 \ge \cdots$.

Solution

The generation proceeds by constructing the sequence $a_1, a_2, \ldots$ left to right, while maintaining three invariants at every stage $k$.

The first invariant is monotonicity, namely $a_k \le a_{k-1}$, with $a_0 = +\infty$.

The second invariant is the prefix feasibility interval,

$$ \Lambda_k \le S_k \le M_k. $$

The third invariant is extendability: the partial assignment must admit completion to a full partition of $n$ that respects both bounds at all later indices.

At step $k$, assume $a_1, \ldots, a_{k-1}$ are fixed, with prefix sum $S_{k-1}$ and remaining sum $R = n - S_{k-1}$. The next value $a_k$ is chosen within bounds derived from the majorization constraints.

The lower constraint comes from all inequalities $\Lambda_t \le S_t$ for $t \ge k$. Writing $S_t = S_{k-1} + a_k + (t-k)\cdot 0$ as a minimal continuation is invalid because future parts may increase the prefix sum. The tightest safe bound uses the fact that future parts are at most $a_k$ due to monotonicity, so for $t \ge k$,

$$ S_t \le S_{k-1} + (t-k+1)a_k. $$

Thus feasibility of all lower bounds requires

$$ S_{k-1} + (t-k+1)a_k \ge \Lambda_t, $$

hence

$$ a_k \ge \frac{\Lambda_t - S_{k-1}}{t-k+1}. $$

The upper constraint comes directly from $\mu$, since for all $t \ge k$,

$$ S_t \le M_t, $$

and in particular $S_k \le M_t$, so

$$ a_k \le M_t - S_{k-1}. $$

Monotonicity adds $a_k \le a_{k-1}$, and nonnegativity gives $a_k \ge 0$.

Combining all constraints yields the interval

$$ L_k = \max\left(0, \max_{t \ge k} \left\lceil \frac{\Lambda_t - S_{k-1}}{t-k+1} \right\rceil \right), $$

$$ U_k = \min\left(a_{k-1}, \min_{t \ge k} (M_t - S_{k-1}), R\right). $$

If $L_k > U_k$, no continuation exists from the current prefix, so the branch terminates.

Otherwise, each integer choice $a_k \in [L_k, U_k]$ is explored, with update

$$ S_k = S_{k-1} + a_k, \qquad R \leftarrow R - a_k. $$

When $R = 0$, a full partition has been produced and is output.

The resulting recursive procedure is:

At level $k$, given $a_1, \ldots, a_{k-1}$, compute $L_k$ and $U_k$ as above. For each $a_k$ in descending order from $U_k$ to $L_k$, assign $a_k$, update prefix sums, and recurse to $k+1$.

Correctness follows from two directions.

Every generated sequence satisfies $\lambda \preceq \alpha \preceq \mu$ because each step enforces all inequalities $\Lambda_t \le S_t \le M_t$ for all $t \ge k$, and monotonicity ensures a valid partition structure.

Conversely, let $\alpha$ be any partition with $\lambda \preceq \alpha \preceq \mu$. For each $k$, the value $a_k$ satisfies all derived bounds because the inequalities defining $L_k$ and $U_k$ are necessary consequences of the prefix constraints applied to $\alpha$. Thus $\alpha$ is never pruned and is generated by the recursion.

This completes the proof. ∎

Verification

The construction enforces the defining majorization inequalities at every prefix length, since $L_k$ is obtained from all lower-bound constraints $\Lambda_t \le S_t$ and $U_k$ is obtained from all upper-bound constraints $S_t \le M_t$. Monotonicity is preserved by the explicit condition $a_k \le a_{k-1}$.

Termination occurs because each recursive call fixes one additional part and reduces the remaining sum, so the process cannot descend indefinitely.

Every feasible extension is retained because the bounds are derived only from necessary conditions satisfied by every valid completion, so no valid partition is excluded.

Notes

The same framework specializes to classical constrained partition generation. Taking $\lambda$ as the lexicographically smallest partition with prescribed bounds and $\mu$ as the largest converts the interval $\lambda \preceq \alpha \preceq \mu$ into standard “box-constrained” partitions, including fixed-length or bounded-part problems discussed in the note of the exercise.