469,963 Members | 1,943 Online

Partitions of an integer

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[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)
Jul 18 '05 #1
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(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.
Jul 18 '05 #2
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
Jul 18 '05 #3
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 [i]+parts

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

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

Heiko.
Jul 18 '05 #4
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
Jul 18 '05 #5
* 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

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>

--
DW
Jul 18 '05 #6

 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 1 post views Thread by Nepomuk | last post: by reply views Thread by eddparker01 | last post: by reply views Thread by eddparker01 | last post: by reply views Thread by lanliddd | last post: by reply views Thread by isladogs | last post: by 1 post views Thread by isladogs | last post: by 2 posts views Thread by elpidahope | last post: by 1 post views Thread by IbrarBarlow | last post: by 1 post views Thread by mscomx | last post: by reply views Thread by Abraham01 | last post: by