Partition Problem

[Alex Martelli]

"Donovan Hide" <donovanhide at bigfoot.com> wrote in message
news:9itb14$2oi$1 at newsg1.svr.pol.co.uk...
    ...
> question. What I am actually looking for is the enumeration of all the 6
> whole numbers greater than 0 that sum to 17.
>     After that, another enumeration is required, this time to find all 6
> whole numbers greater than 0 that sum to 20. Order is unimportant.
    ...
>     So, apart from this short bibliography, I am still stuck. I don't want

So go back to the solution I already posted for a slightly
different interpretation of your problem:

def seqs(i, j, sumsofar, sumdesired, minok, thelist):
    # print 's',i,j,sumsofar,sumdesired,minok,thelist[:j]
    if i==j-1:
        missing = sumdesired - sumsofar
        if missing < minok: return 0
        thelist[i] = missing
        print thelist
        return 1
    elif i>=j or sumsofar+minok > sumdesired:
        return 0
    thelist[i] = minok
    results = 0
    while 1:
        more = seqs(i+1, j, sumsofar+thelist[i], sumdesired,
            thelist[i]+1, thelist)
        if not more: break
        results += more
        thelist[i]+=1
    return results

Apparently the only way in which this differs from what
you'd like to do is that this forbids duplication, right?
OK, then, so ALLOW duplication -- where's the problem?!
Just change the recursive call so that the 5th parameter,
'minok', is passed as thelist[i] rather than thelist[i]+1.

This means thelist ends up in nondecreasing, rather than
strictly increasing, order.

def seqs1(i, j, sumsofar, sumdesired, minok, thelist):
    # print 's',i,j,sumsofar,sumdesired,minok,thelist[:j]
    if i==j-1:
        missing = sumdesired - sumsofar
        if missing < minok: return 0
        thelist[i] = missing
        print thelist
        return 1
    elif i>=j or sumsofar+minok > sumdesired:
        return 0
    thelist[i] = minok
    results = 0
    while 1:
        more = seqs1(i+1, j, sumsofar+thelist[i], sumdesired,
            thelist[i], thelist)
        if not more: break
        results += more
        thelist[i]+=1
    return results

if __name__=='__main__':
    nr = seqs1(0, 6, 0, 17, 1, 6*[0])
    print nr,'sets of 6 numbers that sum to 17'

D:\py21>python sq.py
[1, 1, 1, 1, 1, 12]
[1, 1, 1, 1, 2, 11]
    ...snipped several lines...
[2, 2, 3, 3, 3, 4]
[2, 3, 3, 3, 3, 3]
44 sets of 6 numbers that sum to 17

D:\py21>


So, where's the problem?  Solving this for sets of 6
numbers that sum to 20 is left as an exercise for the
reader -- not too difficult an exercise, I hope!-)
(More interesting is to find optimizations that can
be applied to this reference implementation:-).

Another easy exercise: what would you change if the
numbers were allowed to be from -1 upwards, rather
than "greater than 0"...?


General consideration: even where the problem statement
does NOT constrain the order of the results (you just
have to count them, whatever), it's often easier if
results are generated in a systematic order -- this helps
ensure against double-counting, you can print out the
results you're supposed to be just-counting to help
you debug things (and notice gaps more easily because
of the systematic order, if you have a bug somewhere)...


Alex