For $ p_k(n) $, the partitions of $ n $ with exactly $ k $ parts, it's possible to order them such that each adjacent pair of partitions differ only by one, i.e. one can be transposed to the other by subtracting 1 from one of its parts and adding 1 to another.
$$ p_4(8)\\ \{5, 1, 1, 1\}\\ \{4, 2, 1, 1\}\\ \{3, 3, 1, 1\}\\ \{3, 2, 2, 1\}\\ \{2, 2, 2, 2\}\\ $$
This (and its reverse) is the only ordering of $ p_4(8) $ with this property. $ p_5(10) $, $ p_6(12) $, and others also have unique orderings like this, but as $n$ and $k$ increase, $ p_k(n) $ has many more orderings that meet this criterion.
My questions are:
- Is there a procedure to generate one of these orderings for $ p_k(n) $? I can generate all $k$-sized partitions and look for a Hamiltonian path within them, but I'm hoping there's a smarter, faster approach.
- Can any of these orderings be thought of as canonical? Some thought has been given to orderings of partitions, but I can't find an ordering with this property.
I think Carla Savage's 1989 paper "Gray Code Sequences of Partitions" (Journal of Algorithms 10, 577-595) does what you need. There are two primary algorithms, some trickier work when $n$ is close to double the number of parts (as in the examples you've mentioned), and a few special cases. Most of the work is done on $P(n,k)$ defined as partitions of $n$ into at most $k$ parts, whereas you want exactly $k$ parts. Towards the end, though, she explains that the algorithm guarantees the exactly $k$ parts result as well. Whether the order is canonical may be a matter of taste, as the algorithm is a bit complicated.
To see more about related problems, Torsten Mütze recently posted Combinatorial Gray codes - an updated survey to the arXiv.