Partitions of an integer

[Heiko Wundram]

Am Samstag, 24. Juli 2004 18:08 schrieb Nick J Chackowsky:
> My method, however, generates plenty of duplicates (note the if
> statement to catch them). Generating the 15 partitions of 7, for
> example, also generates 19 duplicates. Can someone spot a way to improve
> or eliminate the duplicates?

def _yieldParts(num,lt):
    if not num:
        yield []
    for i in range(min(num,lt),0,-1):
        for parts in yieldParts(num-i,i):
            yield [i]+parts

def yieldParts(num):
    for part in _yieldParts(num,num):
        yield part

parts = list(yieldParts(7,7))
print len(parts)
print parts

will only yield non-duplicate partitions, and functions as a generator, so you 
don't need to store all partitions in memory. It's not iterative as your 
example, but you could implement caching so that its runtime decreases to 
iterative.

Heiko.