Recipe19.16.Generating the Partitions of an Integer


Recipe 19.16. Generating the Partitions of an Integer

Credit: David Eppstein, Jan Van lent, George Yoshida

Problem

You want to generate all partitions of a given positive integer, that is, all the ways in which that integer can be represented as a sum of positive integers (for example, the partitions of 4 are 1+1+1+1, 1+1+2, 2+2, 1+3, and 4).

Solution

A recursive generator offers the simplest approach for this task, as is often the case with combinatorial computations:

def partitions(n):     # base case of the recursion: zero is the sum of the empty tuple     if n == 0:         yield ( )         return     # modify the partitions of n-1 to form the 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, combinations and selections, are among the most basic primitives of combinatorial arithmetic. In other words, such constructs, besides being useful on their own, are building blocks for generating other kinds of combinatorial objects.

This recipe works along classic recursive lines. If you have a partition of a positive integer 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. For example, you can build partitions of 5 from partitions of 6 by such transformation steps as 1+2+3 => 2+3, 2+4 => 1+4, and so forth. The algorithm in this recipe reverses the process: for each partition p of n-1, the algorithm finds the partitions of n that would be reduced to p by this canonical transformation step. Therefore, each partition p of n is output exactly once, at the step when we are considering the partition p1 of n-1 to which p canonically reduces.

Be warned: the number of partitions of n grows fast when n itself grows. Ramanujan's upper bound for the number of partitions of a positive integer k is:

    int(exp(pi*sqrt(2.0*k/3.0))/(4.0*k*sqrt(3.0)))

(where names exp, pi and sqrt are all taken from module math, in Python terms). For example, the number 200 has about 4,100 billion partitions.

This recipe generates each partition as a tuple of integers in ascending order. If it's handier for your application to deal with partitions as tuples of integers in descending order, you need only change the body of the for loop in the recipe to:

    yield p + (1,)     if p and (len(p) < 2 or p[-2] > p[-1]):         yield p[:-1] + (p[-1] + 1,)

Creating a new tuple per item in the output stream, as this recipe does, may result in performance issues, if you're dealing with a very large n. One way to optimize this aspect would be to return lists instead of tuples, and specifically to return the same list object at each step (with the descending-order modification, and append and pop operations rather than list concatenation):

def partfast(n):     # base case of the recursion: zero is the sum of the empty tuple     if n == 0:         yield [  ]         return     # modify the partitions of n-1 to form the partitions of n     for p in partfast(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

This optimization is not worth the bothernot so much because of the modest extra complication in partfast's own code, but mostly because yielding the same list object at each step means that code using partfast must take precautions. For example, list(partfast(4)) is a potentially surprising list of five empty sublists, while list(partitions(4)) is exactly the expected list of the five partitions of the number 4.

On the "other" hand, a different approach using an auxiliary parameter can actually produce a simplification for the descending-order case:

def partitions_descending(num, lt=num):     if not num: yield ( )     for i in xrange(min(num, lt), 0, -1):         for parts in partitions_descending(num-i, i):             yield (i,) + parts

This code is simpler than the variant given in the recipe and could be made even clearer in Python 2.4 by changing its outer loop into:

    for i in reversed(xrange(1, min(num, lt)-1)):

See Also

Recipe 19.15 for more combinatorics building blocks.



Python Cookbook
Python Cookbook
ISBN: 0596007973
EAN: 2147483647
Year: 2004
Pages: 420

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net