Partition Problem

[Tom Good]

"Donovan Hide" <donovan at sherbet.co.uk> wrote in message news:<tlavt7jeqqt7b3 at corp.supernews.co.uk>...
> Wow,
>     fascinating! The minds of two 'algorthmistas' battling the pros and cons
> of there code and techniques. I can't tell you how interesting this is. I
> really get the feeling that Python needs a good combinatorics module.
> CombPy, maybe?

[snip]

And now, for something completely different!  "Fun with generators."

Here is the "sets of 6 positive integers that sum to 17" problem,
solved with generators.  Works with Python 2.2.  My goal here was to
minimize lines of code, not to optimize for performance.


Tom


# -------- begin code

from __future__ import generators
import operator

def genSet(howMany, minNum, maxNum): # generator
    if howMany <= 1:
        for i in range(minNum ,maxNum+1): yield [i]
    else:
        for a in genSet(howMany-1, minNum, maxNum):
            for b in range(max(a), maxNum+1):
                yield a + [b]

def findSum(howMany, minNum, maxNum, sum): # generator
    for i in genSet(howMany, minNum, maxNum):
        if reduce(operator.add, i) == sum:
            yield i
            

if __name__ == "__main__":
    print "finding sets of 6 positive integers that add up to 17" 
    count = 0
    for i in findSum(6, 1, 17, 17):
        count += 1
        print count, ":", i

# -------- end code

Running it:

C:\Python22>python testgen.py
finding sets of 6 positive integers that add up to 17
1 : [1, 1, 1, 1, 1, 12]
2 : [1, 1, 1, 1, 2, 11]
3 : [1, 1, 1, 1, 3, 10]
4 : [1, 1, 1, 1, 4, 9]
5 : [1, 1, 1, 1, 5, 8]
6 : [1, 1, 1, 1, 6, 7]
7 : [1, 1, 1, 2, 2, 10]
8 : [1, 1, 1, 2, 3, 9]
9 : [1, 1, 1, 2, 4, 8]
10 : [1, 1, 1, 2, 5, 7]
11 : [1, 1, 1, 2, 6, 6]
12 : [1, 1, 1, 3, 3, 8]
13 : [1, 1, 1, 3, 4, 7]
14 : [1, 1, 1, 3, 5, 6]
15 : [1, 1, 1, 4, 4, 6]
16 : [1, 1, 1, 4, 5, 5]
17 : [1, 1, 2, 2, 2, 9]
18 : [1, 1, 2, 2, 3, 8]
19 : [1, 1, 2, 2, 4, 7]
20 : [1, 1, 2, 2, 5, 6]
21 : [1, 1, 2, 3, 3, 7]
22 : [1, 1, 2, 3, 4, 6]
23 : [1, 1, 2, 3, 5, 5]
24 : [1, 1, 2, 4, 4, 5]
25 : [1, 1, 3, 3, 3, 6]
26 : [1, 1, 3, 3, 4, 5]
27 : [1, 1, 3, 4, 4, 4]
28 : [1, 2, 2, 2, 2, 8]
29 : [1, 2, 2, 2, 3, 7]
30 : [1, 2, 2, 2, 4, 6]
31 : [1, 2, 2, 2, 5, 5]
32 : [1, 2, 2, 3, 3, 6]
33 : [1, 2, 2, 3, 4, 5]
34 : [1, 2, 2, 4, 4, 4]
35 : [1, 2, 3, 3, 3, 5]
36 : [1, 2, 3, 3, 4, 4]
37 : [1, 3, 3, 3, 3, 4]
38 : [2, 2, 2, 2, 2, 7]
39 : [2, 2, 2, 2, 3, 6]
40 : [2, 2, 2, 2, 4, 5]
41 : [2, 2, 2, 3, 3, 5]
42 : [2, 2, 2, 3, 4, 4]
43 : [2, 2, 3, 3, 3, 4]
44 : [2, 3, 3, 3, 3, 3]