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.a ppend(onepartit ion)

# p steps through allpartitions, looking for those which are not all 1s
p = 0
while p != len(allpartitio ns):
onepartition = allpartitions[p]
# check each element of this partition
i = 0
while i != len(onepartitio n):
# if there is a non-1, 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.so rt()
newpartition.re verse()
# newpartition may be a copy of an existing one!!!
if not newpartition in allpartitions:
allpartitions.a ppend(newpartit ion)
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,l t),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.

[George Yoshida]

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

[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,l t),0,-1): - for parts in yieldParts(num-i,i):
+ 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

Heiko.

[Michael J. Fromberger]

In article <pN************ **@animal.nntps erver.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_part itions(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

[Damien Wyart]

* Nick J Chackowsky <me************ *@hotmail.com> in comp.lang.pytho n:

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.Stanfor d.EDU/~knuth/fasc3b.ps.gz>

--
DW