Welcome to MathOverflow

Question

4

1

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?

flag	asked Apr 18 2011 at 8:45 Ben Lerner 95●3

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

AVS · Accepted Answer · 2011-04-18 11:59:51Z UTC

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

Mircea · Answer 2 · 2012-11-30 21:32:47Z UTC

0

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.

answered Nov 30 at 21:32

Mircea
1

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.