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