Partitions of an integer

[Michael J. Fromberger]

In article <pNvMc.381$KU.186 at animal.nntpserver.com>,
 Nick J Chackowsky <mediocre_person at 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