# Get all possible partitions of number

Is there a way to get all possible partitions of an integer? Possibly specifying max and/or min summand. I'm interested in partitions themselves, not just partition count.

-
You can do an algorithm, if you are patient, but there isn't (known) any formula to compute it. It's interesting that for the first integers you get prime numbers. –  Diego Silvera Feb 10 '13 at 2:11
@Diego, an algorithm is a formula is an algorithm, no? –  Gerry Myerson Feb 10 '13 at 2:16
@GerryMyerson By formula I mean an elementary function known. –  Diego Silvera Feb 10 '13 at 2:21

This is Perl:

sub partition {
print "@_\n";
my ($largest, @rest) = @_; my$min = $rest[0] || 1; my$max  = int($largest/2); for my$n ($min ..$max) {
partition($largest-$n, \$n, @rest);
}
}


The code should be easy to translate into other languages, once you know that @_ is Perl's notation for the list of arguments to a function. To invoke, use something like

partition(6)


which will produce the output

6
5 1
4 1 1
3 1 1 1
2 1 1 1 1
1 1 1 1 1 1
2 2 1 1
3 2 1
4 2
2 2 2
3 3


Simple tinkering with the function will produce the outputs in other orders, possibly more useful.

Chapter 5 of Higher-Order Perl has an extensive discussion of this function.

-

The book "Combinatorial Algorithms. For Computers and Calculators. Second Edition" by ALBERT NIJENHUIS and HERBERT S. WILF is available in pdf at http://www.math.upenn.edu/~wilf/website/CombinatorialAlgorithms.pdf . It has algorithms for many combinatorial computations including generating all partitions of an integer.

Lots of good stuff here, but beware the sometimes hard to understand fortran. Its heapsort routine does it in 22 lines of non-recursive fortran.

-
Thanks, sounds like worth to take a look! –  Nordvind Feb 10 '13 at 10:46