Skip to main content
MathOverflow

Return to Answer

corrected spelling, minor clarification
Source Link
AVS
AVS
  • 751
  • 6
  • 8

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 integersinteger $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 numbersize of partitions it outputsthe output).

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 integers $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 number of partitions it outputs).

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

Source Link
AVS
AVS
  • 751
  • 6
  • 8

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 integers $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 number of partitions it outputs).