There is a natural way to order all $k=1..p(N)$ partitions of a given integer $N$ ($p(N)$ being a total number of partitions) in a "decreasing" order. Say, for $4$: $$ \{4\},\,\{3,1\},\,\{2,2\},\,\{2,1,1\},\,\{1,1,1,1\}\,. $$ (I think, it's pretty clear how the ordering is defined here.)

I'm wondering if there's a known way to reconstruct the partition from its number $k$ in this sequence, and, vice versa, to determine $k$ by looking at the partition?

  • $\begingroup$ If you consider it an easy step to calculate this quantity then you can do a search (at least a linear search, possibly some form of binary search) based on finding the max element, then recurse down. $\endgroup$ – antkam Apr 20 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.