Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 6 down vote accepted

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).

share|improve this answer

See Fast Algorithm for Generating Ascending Compositions in Journal of Mathematical Modelling and Algorithms, 11(1), 89-104 (2012) DOI: 10.1007/s10852-011-9168-y.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.