SimpleBlog

The Partition Function implemented in Ruby and Python

I did a search and did not find a implementation, so I did my own. But I am sure there are more efficient implementations in other languages.

Partition of n is shown here:

Partions for 1:

[1]

Partions for 2:

[2]

[1, 1]

Partions for 3:

[3]

[2, 1]

[1, 1, 1]

Partions for 4:

[4]

[3, 1]

[2, 2]

[2, 1, 1]

[1, 1, 1, 1]

Partions for 5:

[5]

[4, 1]

[3, 2]

[3, 1, 1]

[2, 2, 1]

[2, 1, 1, 1]

[1, 1, 1, 1, 1]

and so on.

So this is nice and has a lot of applications, but I was interessted in the numbers of partitions, which are: 1, 2, 3, 5, 7, 11, 15, 22, 30, 42 and so on (starts harmless, but increases very rapidly ;-).

Take a look at: Weisstein, Eric W. Partition Function P. From MathWorld—A Wolfram Web Resource.

or at:

Wikipedia (number_theory)

Ruby

I found an Euler based (pfeulerrec) recursive function that calculates the partition function of n: Weisstein, Eric W. Partition Function P. From MathWorld—A Wolfram Web Resource.

In the following Ruby Script I tried this one first, but recognized, that it is not usefull. It is mathematically usefull but computational too complex.

So I looked at the patterns upside and saw, that there is a very easy way to compute the numbers if you can remember some numbers (n**2). So remembering is perfect for hashing.

And I did it like most of the time: Prototyping in Ruby, cause this is the best language for writing down what you think (at least for hummingbird minds) and reimplementing it in Python, cause it is still faster and beter for clear structured thinkers (which for gods sake not every body is ;-). Hey I love Python and Ruby too.

So the Ruby version works quite well up to some 100s.

#!/bin/ruby

# don't call pfeulerrec for n >28 !
def pfeulerrec(n)
  return 1 if n==0
  return 1 if n==1
  r=0
  (1..n).each do |k|
    r+=((-1)**(k+1))*(pf(n-((k*(3*k-1))/2))+pf(n-((k*(3*k+1))/2)))
  end
  r
end

def listcountpartitions(m)
  parth=Hash.new(0)
  pl=Array.new
  (1..m).to_a.each do |n|
    parth[[n,n]]=1
    pf=1
    (1...n).to_a.each do |s|
      h=n-s
      su=0
      (1..s).to_a.each do |i|
        su+=parth[[h,i]] if i <= h
      end
      parth[[n,s]]=su
      pf+=su
    end
    pl << pf
  end
  pl
end

def countpartitions(m)
  parth=Hash.new(0)
  (1..m).to_a.each do |n|
    parth[[n,n]]=1
    @pf=1
    (1...n).to_a.each do |s|
      h=n-s
      su=0
      (1..s).to_a.each do |i|
        su+=parth[[h,i]] if i <= h
      end
      parth[[n,s]]=su
      @pf+=su
    end
  end
  @pf
end

p listcountpartitions(10)
#--> [1, 2, 3, 5, 7, 11, 15, 22, 30, 42]
p countpartitions(100)
#--> 190569292

Python

Better for the range some 100s up to some 1000s. And I added a generator.

def gencountpartitions():
    n=1
    parth={}
    while 1:
        parth[(n,n)]=1
        pf=1
        for s in range(1,n):
            h=n-s
            su=0
            for i in range(1,s+1):
                if i<=h:
                    su+=parth[(h,i)]
            parth[(n,s)]=su
            pf+=su
        yield pf
        n+=1

def listcountpartitions(m):
    parth={}
    pl=[]
    for n in range(1,m+1):
        parth[(n,n)]=1
        pf=1
        for s in range(1,n):
            h=n-s
            su=0
            for i in range(1,s+1):
                if i<=h:
                    su+=parth[(h,i)]
            parth[(n,s)]=su
            pf+=su
        pl.append(pf)
    return pl

def countpartitions(m):
    parth={}
    for n in range(1,m+1):
        parth[(n,n)]=1
        pf=1
        for s in range(1,n):
            h=n-s
            su=0
            for i in range(1,s+1):
                if i<=h:
                    su+=parth[(h,i)]
            parth[(n,s)]=su
            pf+=su
    return pf

print listcountpartitions(10)
#--> [1, 2, 3, 5, 7, 11, 15, 22, 30, 42]
print countpartitions(100)
#--> 190569292

pf=gencountpartitions()
for i in range(2000):
    print pf.next()
#--> 1
# ...
#--> 4720819175619413888601432406799959512200344166

Ok the range 2000 will last a while. So change to 1000 if 10 minutes is to long for you.