# Is there a good known algorithm for generating sets of monomials? (Alternatively, what is the fastest known algorithm for generating integer partitions?)

I'm interested in efficiently generating (or iterating over) sets of all monomials of a degree $n$ over $r$ variables,, up to relabeling variables; this can be identified with the set of partitions of $n$ into at most $r$ parts.

More generally, I need to efficiently generate (or iterate over) the set of all sets of $k$ distinct monomials of degree $n$ over $r$ variables, up to relabeling variables. I can think of a few ways to solve both problems, but nothing that isn't extremely computationally intensive. Are there good known algorithms for these computations?

-
For what it's worth, you can try looking at the bottom of this page math.ias.edu/~bober –  Vasu vineet Apr 18 '11 at 16:54

See Chapter 7.2.1.4 of Knuth "The Art of Computer Programming" Vol. 4 Fascicle 3. On page 38 he gives algorithms to efficiently enumerate all partitions of an integer $n$ (see Algorithm P), or to enumerate all partitions of $n$ into exactly $m$ parts (see Algorithm H). Running Algorithm H repeatedly with $m$ varying from 1 to $r$ should solve your problem in essentially optimal time (i.e. within a constant factor of the size of the output).