Get all possible partitions of number

Question

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.

Answer 1

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.

---

Here it is in Python:

def partition(largest, *rest):
    print(largest, *rest)
    min = rest[0] if rest else 1
    max = largest // 2
    for n in range(min, max+1):
        partition(largest-n, n, *rest)

Answer 2

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.