Partitions of an Integer
The subject of integer partitions comes up regularly, with multiple threads over the years at PerlMonks, a big chunk of Chapter 5 of Higher-Order Perl, and some pages from Knuth TAOCP volume 4A. Last year I added a partitions function to my ntheory Perl module, for counting integer partitions (OEIS A000041). A few months ago I added a partition iterator (forpart) since I liked the one Pari/GP added last year.
Solution | Impl | Order anti-lex |
Order lexico |
Restrict count |
Restrict size |
Max in 10s | Count in 10s |
---|---|---|---|---|---|---|---|
ntheory 0.45 | XS | yes | no | yes | yes | 87 | 223,000 |
ntheory 0.45 | Perl | yes | no | yes | yes | 72 | 7,300 |
Integer::Partition 0.05 | Perl | yes | yes | no | no | 67 | - |
(unreleased, from Limbic 2004) |
Perl | no | yes | no | no | 62 | 6,000 |
MJD 2013 | Perl | no | no | no | no | 71 | - |
blokhead 2007 | Perl | yes | no | no | no | 63 | - |
kvale 2004 | Perl | yes | no | no | no | 62 | - |
sfink 2004 | Perl | yes | no | no | no | 58 | - |
tye 2001 | Perl | no | no | no | no | 58 | - |
(golfed, 73 chrs) |
Perl | no (73) yes(90) |
no | no | no | 21 | - |
Pari/GP 2.8.0 (not a Perl module!) |
C/Pari | no | no | yes | yes | 100 | 34,000,000 |