Partition Problem

[Alex Martelli]

"Peter Hansen" <peter at engcorp.com> wrote in message
news:3B4FBEA0.D5A6DC8A at engcorp.com...
    ...
> If you have algorithms, why not post them?  Are you hoping somebody
> will write this from scratch just for you?  (Someone might, but he's
> in a different timezone and wasting his time creating it.comp.lang.python,

free.it.python, actually, so the time isn't wasted -- the newsgroup is
working just fine:-).

> and _still_ hasn't replied since you posted this 13 hours ago, so you
> might be out of luck. :)

Actually I _was_ tempted to comment that no set can sum to
both 17 and 20, too, but I manfully resisted temptation... until
you implicitly called on me...:-).

To make such problems as "sets of N numbers that sum to X"
meaningful we need much more precise specifications.  If the
numbers are allowed to be negative, there are of course an
infinite number of such sets, although it could be interesting
to try to qualify the sets into a finite number of parametric
families.  Are the numbers to be >0, >=0, is repetition among
them allowed (or are they to be SETS in the strict sense, where
'repetition of membership' is meaningless)...?

A highly constrained definition (numbers from 1 upwards, no
repetition) may be the most interesting one.  Given a list of
N-1 such numbers monotonically growing (without loss of
generality, since no repetition is allowed) the N-th number is
trivially obtained a X-the sum of the others with the constraint
of strict monotonical growth.  Thinking backwards to N-2,
N-3, etc, we see that for a given fixed prefix of N-m numbers
the last of which is K the solutions are the m-length suffixes
of numbers K+1 and up that sum to X-(sum of the first N-m).

Recursively, then, and without much worry at optimizing...:

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

if __name__=='__main__':
    nr = seqs(0, 6, 0, 23, 1, 6*[0])
    print nr,'sets'

D:\MinGw32>python su.py
[1, 2, 3, 4, 5, 8]
[1, 2, 3, 4, 6, 7]
2 sets

D:\MinGw32>

Now the interesting parts are such things as removing
recursion, proving correctness, seeing what optimizations
if any can be afforded, and so on...

Ah, combinatorics IS fascinating indeed...!!!


Alex