ActiveState Code

Recipe 218332: Generator for integer partitions

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 
 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:]

Discussion

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.

Comments

  1. 1. At 9:22 a.m. on 6 sep 2003, David Eppstein (the author) said:

    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.

  2. 2. At 3:59 p.m. on 11 sep 2003, Jan Van lent said:

    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)))
  3. 3. At 8:22 p.m. on 5 jan 2004, George Yoshida said:

    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].
  4. 4. At 11:59 a.m. on 24 jul 2004, Heiko Wundram said:

    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.

  5. 5. At 6:15 p.m. on 8 may 2005, Tim Peters said:

    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
  6. 6. At 3:01 a.m. on 16 mar 2006, Jan Van lent said:

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

    See also http://www.cs.sunysb.edu/~algorith/files/generating-partitions.shtml

Sign in to comment