Partition of a positive integer N

Question

Find the number of partitions of a positive integer n. Hope someone uses the explicit finite formula for the partition function defined in Jan Hendrik Brunier and Ken Ono paper here.

Sample Input
8
Sample Output
22

N is less than or equal to 1000. Write the complete program. More than anything I would like to see the different approaches.

Answer 1

Java Solution

 public class IntegerPartition {
        public static void main(String[] args) {
            int n = 8; //set integer here!!
            int[][] a = new int[n + 1][n + 1];
            int i, j, k;
            for (i = 0; i < a.length; i++) {
                a[i][0] = 0;
                a[0][i] = 1;
            }
            for (i = 1; i < a.length; i++) {
                a[i][1] = 1;
                for (j = 2; j < a[0].length; j++) {
                    k = i - j;
                    if (k < 0)
                        a[i][j] = a[i][j - 1];
                    else
                        a[i][j] = a[i][j - 1] + a[k][j];
                }
            }
            i--;
            int answer = a[i][i - 1];
            System.out.println(answer + 1);
        }
    }

Answer 2

Python (109 89)

n=input()
s=0
l=[(n,n)]
while l:a,i=l.pop(0);s+=a==0;l+=[(a-i,i),(a,i-1)]*(a*i>0)
print s

Answer 3

APL, 23 characters

{⍵=0:1⋄+/⍵(-∇¨⍨⊢⌊-)⍳⍺}⍨

Answer 4

Mathematica 11 chars

Sorry, no need to implement the algorithm

PartitionsP  

Usage

%[8]  
22

Answer 5

Ruby - 95 chars

Based on Hoa Long Tam's solution

s=0
l=[[n=gets.to_i,n]]
(a,i=l.pop;a>0&&i>0&&l+=[[a-i,i],[a,i-1]];a==0&&s+=1)until l==[]
p s

Answer 6

Perl, 92 chars

Recursive solution using p(k,n) = number of partitions of n using numbers >= k. Uses dynamic programming and partitions 1000 in 2s on my machine.

sub p{my($k,$n)=@_;$c{$k,$n}||($c{$k,$n}=$k<$n?p($k+1,$n)+p($k,$n-$k):$n==$k)}print p(1,pop)

Ungolfed:

sub p {
    my ( $k, $n ) = @_;
    $c{$k,$n}
    || (
        $c{$k,$n} =
        $k < $n
            ? p($k+1,$n) + p($k,$n-$k)
            : $n == $k
    )
}
print p( 1, pop );

Answer 7

Perl, 70 chars

Since there was no time limit:

sub p{my($k,$n)=@_;$k<$n?p($k+1,$n)+p($k,$n-$k):$n==$k}print p(1,pop);

Partitions 50 in 2.3 s.

Answer 8

J, 72

Modified from the manual:

f=:[:(0<@-."1~>@{:)](,([:<@;(-i.)@#([,.(>:{."1)#])&.>]))@]^:[(<i.1 0)"_

eg

#f 8
22

Answer 9

Haskell, 51 39

f=(%1)
0%k=1
n%k=sum[(n-r)%r|r<-[k..n]]

the % function gets two parameters - n and k, and returns the amount of partitions of n at which every part is at least k.

%'s definition works by choosing r to be the next part of the partition. we compute the amount of possibilities when this is the next part (note that all consequent parts must be bigger or equal to it) by a recursive call and sum all possibilities.