Partitions of an integer
Nick J Chackowsky
mediocre_person at hotmail.com
Sat Jul 24 18:08:36 CEST 2004
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)
More information about the Python-list
mailing list