Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Thanks, sounds like worth to take a look! –  Nordvind Feb 10 '13 at 10:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.