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 non1, then create a new partition
if onepartition[i] > 1:
hi = onepartition[i]  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) 5 4064
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(numi,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 nonduplicate 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.
Nick J Chackowsky wrote: 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/Coo.../Recipe/218332
This is a cool example of how to use generators with recursion.

George
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(numi,i):
+ for parts in _yieldParts(numi,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
Heiko.
In article <pN**************@animal.nntpserver.com>,
Nick J Chackowsky <me*************@hotmail.com> wrote: 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] from pprint import pprint pprint(nat_partitions(7))
[(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

Michael J. Fromberger  Lecturer, Dept. of Computer Science http://www.dartmouth.edu/~sting/  Dartmouth College, Hanover, NH, USA
* Nick J Chackowsky <me*************@hotmail.com> in comp.lang.python: 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://wwwcsfaculty.Stanford.EDU/~knuth/fasc3b.ps.gz>

DW This discussion thread is closed Replies have been disabled for this discussion. Similar topics
7 posts
views
Thread by Steve 
last post: by

3 posts
views
Thread by RunLevelZero 
last post: by

6 posts
views
Thread by cantabile 
last post: by

reply
views
Thread by sandeep G 
last post: by

6 posts
views
Thread by Jack Li 
last post: by

3 posts
views
Thread by jcgeorge 
last post: by

11 posts
views
Thread by Claude Henchoz 
last post: by

8 posts
views
Thread by arunrocks 
last post: by
           