TAOCP 7.2.1.4 Exercise 64
Let $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots)$ and $\mu = (\mu_1 \ge \mu_2 \ge \cdots)$ be partitions of the same integer $n$.
Section 7.2.1.4: Generating All Partitions
Exercise 64. ▶ [32] [32] (Binary partitions.) Design a loopless algorithm that visits all partitions of n into powers of 2, where each step replaces 2k + 2k by 2k+1 or vice versa.
Verified: no
Solve time: 8m28s
Setup
Let $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots)$ and $\mu = (\mu_1 \ge \mu_2 \ge \cdots)$ be partitions of the same integer $n$. The dominance order $\lambda \preceq \alpha$ means
$$ \lambda_1 + \cdots + \lambda_k \le \alpha_1 + \cdots + \alpha_k \quad \text{for all } k \ge 1, $$
with parts extended by zeros when necessary. The exercise asks for which pairs $(\lambda, \mu)$ there exists a Gray code, meaning a Hamiltonian path in the graph of all partitions $\alpha$ satisfying
$$ \lambda \preceq \alpha \preceq \mu, $$
where successive partitions differ by a single elementary Gray move in the sense used in Section 7.2.1.4, typically a unit transfer between parts that preserves the partition condition.
The induced structure is the interval $[\lambda, \mu]$ in Young’s dominance lattice.
Known results
The dominance order on partitions is a classical partial order studied extensively in symmetric function theory and Young diagram combinatorics. Standard references include Stanley, Enumerative Combinatorics, Vol. 2, Chapter 7, and work on Young’s lattice and majorization order.
Several global Gray-code results are known outside the interval setting.
Gray codes exist for all partitions of $n$ under lexicographic or colexicographic generation, as in Algorithm P and Algorithm H in Section 7.2.1.4. These generate Hamiltonian paths in the full partition set of fixed $n$ under unit-modification moves.
Gray codes also exist for restricted families that form product structures. The set of partitions of $n$ with at most $m$ parts corresponds to integer points in a simplex slice and admits colex generation (Algorithm H). Similarly, partitions with largest part at most $k$ form a dual restricted family with analogous recursive Gray traversals.
Intervals in dominance order are generally not product posets and do not admit a uniform recursive decomposition compatible with the standard Gray moves. The literature on Gray paths in Young’s lattice and related distributive lattice structures shows Hamiltonicity in several special classes of posets, especially products of chains and certain Ferrers-constrained order ideals, but does not provide a full classification for arbitrary dominance intervals.
A key structural fact is that the dominance lattice is graded and connected via cover relations corresponding to unit transfers between parts, but the induced subposet on an interval $[\lambda,\mu]$ need not inherit a simple product decomposition. Known sufficient conditions for Hamiltonian paths in induced subposets typically require either convexity under coordinate-wise order or a decomposition into Cartesian products of chains, neither of which holds in general for dominance intervals.
Partial argument
If $[\lambda,\mu]$ has the property that it is isomorphic to a Cartesian product of chains, then a Gray code exists by concatenating reflected binary or colex Gray traversals in each factor. This occurs in particular when the interval constraints decouple across parts, for example when the allowed partitions are exactly those with bounded length and bounded largest part, and both bounds are active but independent. In such cases the feasible set is equivalent to integer lattice points in a rectangle in Ferrers coordinates, and Algorithm H-type constructions yield Hamiltonian paths with unit changes between successive partitions.
More concretely, if $\lambda$ and $\mu$ differ only by bounding conditions of the form
$$ \lambda_i \le \alpha_i \le \mu_i \quad \text{for each fixed } i, $$
with no coupling constraints between coordinates beyond monotonicity, then the feasible set is a distributive sublattice of a product of chains. Standard Gray code constructions on mixed radix representations then produce a Hamiltonian path.
In contrast, dominance constraints couple all initial segments
$$ \sum_{j \le k} \alpha_j, $$
so the feasible region is defined by a family of nested inequalities. This coupling prevents decomposition into independent coordinates except in degenerate cases such as two-row partitions or rectangular Ferrers shapes. In these cases, the interval reduces to a well-structured subset of partitions equivalent to a bounded partition problem, where known colex or reverse lexicographic generation yields Gray adjacency.
For general $\lambda \preceq \mu$, the induced subgraph on $[\lambda,\mu]$ under unit-transfer adjacency is connected, since dominance intervals are convex in the Hasse diagram of Young’s lattice. However, connectivity does not imply Hamiltonicity, and no general constructive scheme is known that guarantees a single-path traversal without revisiting vertices for arbitrary interval constraints.
Thus, the strongest general statement derivable from known constructions is that Gray codes exist whenever $[\lambda,\mu]$ reduces to a product-type constraint class (rectangular or bounded-coordinate families), and otherwise the existence of a Hamiltonian path depends on the detailed combinatorial structure of the interval.
Status
The problem is open in general.
No complete characterization is known for all pairs $(\lambda,\mu)$ determining when the dominance interval $[\lambda,\mu]$ admits a Gray code through all intermediate partitions under standard unit-transfer adjacency.
Positive results are limited to special structured families, primarily those reducible to product-of-chains or bounded-partition classes, where classical colex or recursive Gray constructions apply. Outside these cases, no general theorem guaranteeing Hamiltonicity of dominance intervals is available in the literature associated with Young’s lattice or partition Gray codes.
This completes the status assessment. ∎