Dana Jacobsen

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.

This is a look at some different solutions, including two CPAN modules, one unreleased module, and six solutions from forum posts. I also include the latest Pari/GP for comparison. All forum solutions were modified if necessary to take a sub called with the partition. This matches the behavior of the two modules and allows printing, filtering, counting, etc. without modifying the original code. Only iterators were considered, as the number of partitions grows quite rapidly.

For counting, the fastest solutions use the Hardy-Ramanujan-Rademacher formula. The state of the art is Johansson's ARB, which is thousands of times faster than Pari. Pari also uses the Rademacher formula and is quite fast. Jonathan Bober has GPL code using GMP and MPFR that is a little faster than Pari, but MPFR isn't installed on most platforms (meaning it's hard to incorporate into a portable library). I'm using a triangle solution, which isn't too bad in C+GMP compared to Perl's bigints, but way off the fast formula. Integer::Partitions doesn't have a counting method.

ntheory (aka Math::Prime::Util) has a function taking a block (aka an anonymous sub), the number, and an optional hash of restriction parameters. The block is called for each partition with the argument list set to the partition. The restriction parameters are similar to Pari/GP's, with min/max count and min/max element size. This can save quite a bit of time doing filtering (sometimes with shortcuts) inside the XS code.

I debated call by value (a new argument list for each call) vs. call by reference (giving the caller access to internal data). Some XS iterators, e.g. Algorithm::Permute's fast permute, do the latter, and it is faster. I decided on the former because I like the idea that the caller can manipulate its arguments as desired without worrying about segfaults, incorrect iteration, infinite iteration, etc.

Typically the XS code would be used, but there are also pure Perl implementations for everything. They are used if the XS Loader fails, the environment variable MPU_NO_XS exists and is true, or in cases where the arguments would overflow or are not properly parseable.

        use ntheory qw/forpart partitions/;
        forpart { say "@_"; } 8;                     # All partitions of 8
        forpart { say "@_"; } 10,{nmin=>5,amax=>4};  # Only 5+ parts, all <= 4
        say partitions(2000);                        # Counting

The Integer::Partition module has been on CPAN for a number of years, and is the only solution giving both lexicographic and anti-lexicographic ordering choices. It's reasonably fast unless you need larger values with restrictions, or want counts.

        use Integer::Partition;
        my $iter = Integer::Partition->new(8);
        while (my $p = $iter->next) {
          say "@$p";
        }

Math::Pari isn't in the table because it builds with Pari 2.1.7 by default. numbpart (partition count) was added in version 2.2.5 (Nov 2003), and forpart was added in 2.6.1 (Sep 2013). It's possible to build Math::Pari with version 2.3.5 so we could get numbpart but not forpart.

Pari's forpart is quite fast, and has some nice optimizations for restrictions as well. The ordering is by number of elements rather than a lexicographic ordering. The only way to use this from Perl would be a system call to gp.

There are also golfed solutions in under 100 characters. We can even add a callback sub and anti-lexicographic sort and still come in at 93 characters. As usual with heavily golfed code, these are quite slow, managing only 21 partitions in under 10 seconds. This also uses an internal hash for the partitions, which means memory use will grow (though time grows faster so this isn't really an issue).

Here is my simple modification to the golfed solutions, taking 90 characters for integer partitions in anti-lexicographic order with a callback sub. It's very slow however, so just for fun.

sub p{my($s,@e,$o,@f)=@_;@f=sort{$b<=>$a}@e;$_{"@f"}||=$s->(@f);p($s,++$o,@e)while--$e[0]}
p(5);