469,963 Members | 1,943 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,963 developers. It's quick & easy.

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


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>

--
DW
Jul 18 '05 #6

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
11 posts views Thread by Claude Henchoz | last post: by
8 posts views Thread by arunrocks | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.