Partitions of an integer

[Nick J Chackowsky]

Wrote a python script to find the partitions of an integer (a list of
all the ways you can express n as a sum of integers). For example, the
partitions of 5 are
5
4+1
3+2
2+2+1
3+1+1
2+1+1+1
1+1+1+1+1

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?

Nick.

def partitions(n):
"""Create a list of all of n's partitions"""
allpartitions = []
onepartition = [n]
allpartitions.append(onepartition)

# p steps through allpartitions, looking for those which are not all 1s
p = 0
while p != len(allpartitions):
onepartition = allpartitions[p]
# check each element of this partition
i = 0
while i != len(onepartition):
# if there is a non-1, then create a new partition
if onepartition > 1:
hi = onepartition - 1
lo = 1
while hi >= lo:
newpartition = onepartition[:i] + [hi] + [lo] +
onepartition[i+1:]
newpartition.sort()
newpartition.reverse()
# newpartition may be a copy of an existing one!!!
if not newpartition in allpartitions:
allpartitions.append(newpartition)
hi -= 1
lo += 1
i += 1
p += 1
print dups
return allpartitions

print partitions(7)

 

[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 +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.

 

[Heiko Wundram]

Am Samstag, 24. Juli 2004 18:25 schrieb Heiko Wundram:

[snip]

Ahh, slight error crept in:

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

- for parts in yieldParts(num-i,i):
+ for parts in _yieldParts(num-i,i):

yield +parts

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

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

Heiko.

 

[George Yoshida]

Wrote a python script to find the partitions of an integer (a list of
all the ways you can express n as a sum of integers). For example, the
partitions of 5 are
5
4+1
3+2
2+2+1
3+1+1
2+1+1+1
1+1+1+1+1

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?

Nick.

You should check this recipe:

Generator for integer partitions
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/218332

This is a cool example of how to use generators with recursion.

 

[Michael J. Fromberger]

Wrote a python script to find the partitions of an integer (a list of
all the ways you can express n as a sum of integers). For example, the
partitions of 5 are
5
4+1
3+2
2+2+1
3+1+1
2+1+1+1
1+1+1+1+1

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?

Nick.

I propose the following recursive solution:

def sorted(tpl):
copy = list(tpl)[:] ; copy.sort()
return tuple(copy)

def nat_partitions(n, mem = {}):
assert n > 0

if mem.has_key(n):
return mem[n]

parts = {}
for b in range(1, n):
for p in nat_partitions(n - b):
parts[sorted(p + (b,))] = True

mem[n] = parts.keys() + [(n,)]
return mem[n]
[(1, 1, 1, 1, 3),
(1, 1, 2, 3),
(3, 4),
(1, 3, 3),
(1, 2, 4),
(1, 1, 1, 2, 2),
(1, 1, 1, 1, 1, 2),
(1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 4),
(1, 1, 5),
(2, 2, 3),
(2, 5),
(1, 2, 2, 2),
(1, 6),
(7,)]

Certainly the algorithm is simple enough, though there is a certain
amount of thrashing between lists and tuples doing it this way. But,
with the memoization, it performs reasonably well.

-M

 

[Damien Wyart]

Wrote a python script to find the partitions of an integer (a list of
all the ways you can express n as a sum of integers). For example, the
partitions of 5 are
5
4+1
3+2
2+2+1
3+1+1
2+1+1+1
1+1+1+1+1

There have been good answers to your questions in the thread, so I won't
give more Python code here. I just wanted to point out this draft from
Knuth where many details about the theory of partitions and the related
algorithms can be found. I guess this will be of interest for all
contributors of the thread if they do not know this document already.

<http://www-cs-faculty.Stanford.EDU/~knuth/fasc3b.ps.gz>