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

A "partition" is a way of representing a given integer as a sum of zero or more positive integers, e.g. the partitions of 4 are 1+1+1+1, 1+1+2, 2+2, 1+3, and 4. This recipe uses simple generators recursively to produce a stream of all partitions of its argument. Each partition is represented as a sorted list of the numbers to be summed, e.g. [1,1,1,1], [1,1,2], [2,2], [1,3], [4].

Python, 11 lines
 1 2 3 4 5 6 7 8 9 10 11 def partitions(n): # base case of recursion: zero is the sum of the empty list if n == 0: yield [] return # modify partitions of n-1 to form partitions of n for p in partitions(n-1): yield [1] + p if p and (len(p) < 2 or p[1] > p[0]): yield [p[0] + 1] + p[1:]

Partitions, like permutations and combinations, form one of the basic primitives for generating many other kinds of combinatorial object.

One issue with this method is that each item in the output stream is created as a new list object, so the amount of time per step can be linear in n. It would be possible to modify this method so that it reuses the same list for each yielded result, in constant amortized time per step, by using reverse-sorted order for each partition and using push-pop operations, but reusing the same list object could lead to confusion. Additionally, I think the speedup of such a modification would be limited to such large values of n that it wouldn't make sense to try to list all partitions of those numbers.

David Eppstein (author) 20 years, 7 months ago

Explanation. Maybe I should explain in a little more detail how this works. If you have a partition of n, you can reduce it to a partition of n-1 in a canonical way by subtracting one from the smallest item in the partition. E.g. 1+2+3 => 2+3, 2+4 => 1+4. This algorithm reverses the process: for each partition p of n-1, it finds the partitions of n that would be reduced to p by this process. Therefore, each partition of n is output exactly once, at the step when the partition of n-1 to which it reduces is considered.

Jan Van lent 20 years, 7 months ago

Upper bound. The number of partitions grows quickly.

def upper_bound(k):
"""Ramanujan's upper bound for number of partitions of k"""
return int(exp(pi*sqrt(2.0*k/3.0))/(4.0*k*sqrt(3.0)))
George Yoshida 20 years, 3 months ago

Two variations. This recipe is really interesting.

I made two variations on this recipe.

#### tuple version

def partitions_tuple(n):
# tuple version
if n == 0:
yield ()
return

for p in partitions_tuple(n-1):
yield (1, ) + p
if p and (len(p) &lt; 2 or p[1] &gt; p[0]):
yield (p[0] + 1, ) + p[1:]

Each partition is represented as a tuple instead of a list.

This version runs faster than a list equivalent.

#### reverse order

def partitions_rev(n):
# reverse order
if n == 0:
yield []
return

for p in partitions_rev(n-1):
yield p + [1]
if p and (len(p) &lt; 2 or p[-2] &gt; p[-1]):
yield p[:-1] + [p[-1] + 1]

Each partition is represented in descending order.

For example:

4 -&gt; [1,1,1,1], [2,1,1], [2,2], [3,1], [4].
Heiko Wundram 19 years, 9 months ago

Slightly simpler example which generates the sequence from high to low.

def _yieldParts(num,lt):
if not num:
yield ()
for i in range(min(num,lt),0,-1):
for parts in _yieldParts(num-i,i):
yield (i,)+parts

def yieldParts(num):
for part in _yieldParts(num,num):
yield part

This code works just like the given code, but does not create the list from smallest to largest, but rather the other way around. It doesn't need complicated fiddling, and could be sped up considerably by creating a cache for all parts yielded for each num,lt.

Tim Peters 18 years, 11 months ago

Or if you do need speed ... Sometimes I do need speed, and then a multiset representation allows several efficiences, such as O(1) time per iteration (not just amortized O(1)), and compactness (the largest data structure constructed takes O(sqrt(N)) space; the important part of that is there's so much less the partition _consumer_ needs to examine each time -- something to remember next time you find your code endlessly crawling over long strings of ones):

def gen_partitions_ms(n):
"""Generate all partitions of integer n (>= 0).

Each partition is represented as a multiset, i.e. a dictionary
mapping an integer to the number of copies of that integer in
the partition.  For example, the partitions of 4 are {4: 1},
{3: 1, 1: 1}, {2: 2}, {2: 1, 1: 2}, and {1: 4}.  In general,
sum(k * v for k, v in a_partition.iteritems()) == n, and
len(a_partition) is never larger than about sqrt(2*n).

Note that the _same_ dictionary object is returned each time.
This is for speed:  generating each partition goes quickly,
taking constant time independent of n.
"""

if n &lt; 0:
raise ValueError("n must be >= 0")

if n == 0:
yield {}
return

ms = {n: 1}
keys = [n]  # ms.keys(), from largest to smallest
yield ms

while keys != [1]:
# Reuse any 1's.
if keys[-1] == 1:
del keys[-1]
reuse = ms.pop(1)
else:
reuse = 0

# Let i be the smallest key larger than 1.  Reuse one
# instance of i.
i = keys[-1]
newcount = ms[i] = ms[i] - 1
reuse += i
if newcount == 0:
del keys[-1], ms[i]

# Break the remainder into pieces of size i-1.
i -= 1
q, r = divmod(reuse, i)
ms[i] = q
keys.append(i)
if r:
ms[r] = 1
keys.append(r)

yield ms
Jan Van lent 18 years, 1 month ago

list of tuples. This is the same approach as in my recipe 221132.

Chris Smith 12 years, 11 months ago

Here is a modification of Tim's routine that limits the number of partitions to value <= k:

def partitions(n, k=None):
"""Generate all partitions of integer n (>= 0) using integers no
greater than k (default, None, allows the partition to contain n).

Each partition is represented as a multiset, i.e. a dictionary
mapping an integer to the number of copies of that integer in
the partition.  For example, the partitions of 4 are {4: 1},
{3: 1, 1: 1}, {2: 2}, {2: 1, 1: 2}, and {1: 4} corresponding to
[4], [1, 3], [2, 2], [1, 1, 2] and [1, 1, 1, 1], respectively.
In general, sum(k * v for k, v in a_partition.iteritems()) == n, and
len(a_partition) is never larger than about sqrt(2*n).

Note that the _same_ dictionary object is returned each time.
This is for speed:  generating each partition goes quickly,
taking constant time independent of n. If you want to build a list
of returned values then use .copy() to get copies of the returned
values:

>>> p_all = []
>>> for p in partitions(6, 2):
...         p_all.append(p.copy())
...
>>> print p_all
[{2: 3}, {1: 2, 2: 2}, {1: 4, 2: 1}, {1: 6}]

Reference
---------
Modified from Tim Peter's posting to accomodate a k value:
http://code.activestate.com/recipes/218332/
"""

if n < 0:
raise ValueError("n must be >= 0")

if n == 0:
yield {}
return

if k is None or k > n:
k = n

q, r = divmod(n, k)
ms = {k : q}
keys = [k]
if r:
ms[r] = 1
keys.append(r)
yield ms

while keys != [1]:
# Reuse any 1's.
if keys[-1] == 1:
del keys[-1]
reuse = ms.pop(1)
else:
reuse = 0

# Let i be the smallest key larger than 1.  Reuse one
# instance of i.
i = keys[-1]
newcount = ms[i] = ms[i] - 1
reuse += i
if newcount == 0:
del keys[-1], ms[i]

# Break the remainder into pieces of size i-1.
i -= 1
q, r = divmod(reuse, i)
ms[i] = q
keys.append(i)
if r:
ms[r] = 1
keys.append(r)

yield ms
Philip Pham 12 years, 9 months ago

It returns elements going high to low and doesn't create new lists. It runs twice as fast on my computer.

def P(n):
# base case of recursion: zero is the sum of the empty list
if n == 0:
yield []
return

# modify partitions of n-1 to form partitions of n
for p in P(n-1):
p.append(1)
yield p
p.pop()
if p and (len(p) < 2 or p[-2] > p[-1]):
p[-1] += 1
yield p
Chris Smith 7 years, 11 months ago

Or if you need more speed and actually don't mind crawling over ones...

def aP(n):
"""Generate partitions of n as ordered lists in ascending
lexicographical order.

This highly efficient routine is based on the delightful
work of Kelleher and O'Sullivan.

Examples
========

>>> for i in aP(6): i
...
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 2]
[1, 1, 1, 3]
[1, 1, 2, 2]
[1, 1, 4]
[1, 2, 3]
[1, 5]
[2, 2, 2]
[2, 4]
[3, 3]
[6]

>>> for i in aP(0): i
...
[]

References
==========

.. [1] Generating Integer Partitions, [online],
Available: http://jeromekelleher.net/generating-integer-partitions.html
.. [2] Jerome Kelleher and Barry O'Sullivan, "Generating All
Partitions: A Comparison Of Two Encodings", [online],
Available: http://arxiv.org/pdf/0909.2331v2.pdf

"""
# The list `a`'s leading elements contain the partition in which
# y is the biggest element and x is either the same as y or the
# 2nd largest element; v and w are adjacent element indices
# to which x and y are being assigned, respectively.
a = [1]*n
y = -1
v = n
while v > 0:
v -= 1
x = a[v] + 1
while y >= 2 * x:
a[v] = x
y -= x
v += 1
w = v + 1
while x <= y:
a[v] = x
a[w] = y
yield a[:w + 1]
x += 1
y -= 1
a[v] = x + y
y = a[v] - 1
yield a[:w]
Valerio 7 years, 8 months ago

Hi, this is an interesting topic. I have a question: is it possible to have an alghorithm that creates the specific partition combination giving only n and the number of the specific combination ?

Example: the partitions of 4 are:

n.1 is 4
n.2 is 3+1
n.3 is 2+1+1
n.4 is 1+1+1+1

If I need only the combination number 3, ( 2+1+1 ) how can I create it without generating all the partitions ? There is a mathematic formula for this ?

 Created by David Eppstein on Wed, 27 Aug 2003 (PSF)

### Required Modules

• (none specified)