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

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
 ``` 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] != n: # or equivalently p != 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. lalithaprasad 12 years, 8 months ago

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=n; m=1; h=1
yield [x]
while x!=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 11 years ago

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=n; m=1; h=1
yield [x]
while x!=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)

### Required Modules

• (none specified)