Generator for integer partitions (Python recipe) by David Eppstein

ActiveState Code (http://code.activestate.com/recipes/218332/)

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.

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)))

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) < 2 or p[1] > 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) < 2 or p[-2] > p[-1]):
            yield p[:-1] + [p[-1] + 1]

Each partition is represented in descending order.

For example:

4 -> [1,1,1,1], [2,1,1], [2,2], [3,1], [4].

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.

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

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

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

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

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]

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 ?