A "partition" is a way of representing a given integer as a sum of zero or more positive integers, e.g. the partitions of 4 are 1+1+1+1, 1+1+2, 2+2, 1+3, and 4. This recipe uses simple generators recursively to produce a stream of all partitions of its argument. Each partition is represented as a sorted list of the numbers to be summed, e.g. [1,1,1,1], [1,1,2], [2,2], [1,3], .
Python, 11 lines
Partitions, like permutations and combinations, form one of the basic primitives for generating many other kinds of combinatorial object.
One issue with this method is that each item in the output stream is created as a new list object, so the amount of time per step can be linear in n. It would be possible to modify this method so that it reuses the same list for each yielded result, in constant amortized time per step, by using reverse-sorted order for each partition and using push-pop operations, but reusing the same list object could lead to confusion. Additionally, I think the speedup of such a modification would be limited to such large values of n that it wouldn't make sense to try to list all partitions of those numbers.