Recipe 19.16. Generating the Partitions of an IntegerCredit: David Eppstein, Jan Van lent, George Yoshida ProblemYou 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). SolutionA 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:] DiscussionPartitions, 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 AlsoRecipe 19.15 for more combinatorics building blocks. |