4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ For what it's worth, you can try looking at the bottom of this page math.ias.edu/~bober $\endgroup$
    – Vasu vineet
    Commented Apr 18, 2011 at 16:54

2 Answers 2

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .