Python Cookbook 2Nd Edition Jun 1002005 [Electronic resources] نسخه متنی

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.