Welcome, guest | Sign In | My Account | Store | Cart

Generator for integer partitions (iterative version) (Python recipe) by Jan Van lent
ActiveState Code (http://code.activestate.com/recipes/221132/)

An iterative equivalent to the recursive function given in the recipe "Generator for integer partitions" by David Eppstein.

Uses the representation

7 = 17 = 16 + 11 = 15 + 12 = 15 + 2*1 = ...

Python, 22 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def partitions(n):
    if n <= 0: return
    m = int((1 + sqrt(1 + 8 * n)) / 2) - 1
    p = [(1, n)]
    yield p
    while p[-1][0] != n: # or equivalently p[0][1] != 1
        rest = 0
        times, number = p.pop()
        if number == 1:
            rest += times
            times, number = p.pop()
        times -= 1
        rest += number
        if times > 0:
            p.append((times, number))
        number -= 1
        times, rest = divmod(rest, number)
        p.append((times, number))
        if rest > 0:
            p.append((1, rest))
        assert len(p) <= m # preallocation possible
        yield p

Not nearly as elegant as the recursive solution, but maybe easier to implement in some programming languages (C, Fortran).

Replacing "yield" with "print" results in a function that works in python versions without generators. A function "partitions(n, f)" that calls an arbitrary callable object f for each partition, can be obtained by replacing "yield p" by "f(p)".

Changing the algorithm so that the number of ones is stored seperately (not in p) makes it more efficient.

Tags: algorithms

2 comments

lalithaprasad 15 years, 1 month ago  # | flag

While solving problem 76 on projecteuler.net, I came across this link www.site.uottawa.ca/~ivan/F49-int-part.pdf. Given below is the straight forward implementation of ZS1 algorithm in the paper.

def int_part(n):
    x=[1 for i in range(n+1)]
    x[1]=n; m=1; h=1
    yield [x[1]]
    while x[1]!=1:
        if x[h]==2:
            m+=1; x[h]=1; h-=1
        else:
            r=x[h]-1; t=m-h+1; x[h]=r
            while t>=r:
                h+=1; x[h]=r; t-=r
                if t==0: m=h
                else: m=h+1
                if t>1:
                    h+=1; x[h]=t
        yield x[1:m+1]
Chris Smith 13 years, 5 months ago  # | flag

The interpretation of the pseudocode is not quite right. The following was tested for n in range(15) and found to be correct:

def int_part(n):
    x=[1 for i in range(n+1)]
    x[1]=n; m=1; h=1
    yield [x[1]]
    while x[1]!=1:
        if x[h]==2:
            m+=1; x[h]=1; h-=1
        else:
            r=x[h]-1; t=m-h+1; x[h]=r
            while t>=r:
                h+=1; x[h]=r; t-=r
            if t==0:
                m=h
            else:
                m=h+1
                if t>1:
                    h+=1; x[h]=t
        yield x[1:m+1]
Created by Jan Van lent on Thu, 11 Sep 2003 (PSF)
◄ Python recipes (4591) ►
◄ Jan Van lent's recipes (1) ►

Required Modules

  • (none specified)

Other Information and Tasks