Generating the partitions of a number

I needed an algorithm to generate all possible partitions of a positive number, and I came up with one (posted as an answer), but it's exponential time.

The algorithm should return all the possible ways a number can be expressed as the sum of positive numbers less than or equal to itself. So for example for the number 5, the result would be:

• 5
• 4+1
• 3+2
• 3+1+1
• 2+2+1
• 2+1+1+1
• 1+1+1+1+1

So my question is: is there a more efficient algorithm for this?

EDIT: Question was titled "Sum decomposition of a number", since I didn't really know what this was called. ShreevatsaR pointed out that they were called "partitions," so I edited the question title accordingly.

From stackoverflow

• Here's my solution (exponential time) in Python:

  q = { 1: [[1]] }
  
  def decompose(n):
      try:
          return q[n]
      except:
          pass
  
      result = [[n]]
  
      for i in range(1, n):
          a = n-i
          R = decompose(i)
          for r in R:
              if r[0] <= a:
                  result.append([a] + r)
  
      q[n] = result
      return result
  

   

  >>> decompose(5)
  [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
  

• It's called Partitions. [Also see Wikipedia: Partition (number theory).]

  The number of partitions p(n) grows exponentially, so anything you do to generate all partitions will necessarily have to take exponential time.

  That said, you can do better than what your code does. See this, or its updated version in Python Algorithms and Data Structures by David Eppstein.

  Can Berk Güder : Oh, thanks. Wish I knew what it was called before. =) It's funny they don't teach this in Number Theory.

  Can Berk Güder : And I should probably edit the question title accordingly.

  : Thanks for the link to David Eppstein's site, just finished an interesting browsing on his site.

• When you ask to more efficient algorithm, I don't know which to compare. But here is one algorithm written in straight forward way (Erlang):

  -module(partitions).
  
  -export([partitions/1]).
  
  partitions(N) -> partitions(N, N).
  
  partitions(N, Max) when N > 0 ->
      [[X | P]
       || X <- lists:seq(min(N, Max), 1, -1),
          P <- partitions(N - X, X)];
  partitions(0, _) -> [[]];
  partitions(_, _) -> [].
  

  It is exponential in time (same as Can Berk Güder's solution in Python) and linear in stack space. But using same trick, memoization, you can achieve big improvement by save some memory and less exponent. (It's ten times faster for N=50)

  mp(N) ->
      lists:foreach(fun (X) -> put(X, undefined) end,
         lists:seq(1, N)), % clean up process dictionary for sure
      mp(N, N).
  
  mp(N, Max) when N > 0 ->
      case get(N) of
        undefined -> R = mp(N, 1, Max, []), put(N, R), R;
        [[Max | _] | _] = L -> L;
        [[X | _] | _] = L ->
            R = mp(N, X + 1, Max, L), put(N, R), R
      end;
  mp(0, _) -> [[]];
  mp(_, _) -> [].
  
  mp(_, X, Max, R) when X > Max -> R;
  mp(N, X, Max, R) ->
      mp(N, X + 1, Max, prepend(X, mp(N - X, X), R)).
  
  prepend(_, [], R) -> R;
  prepend(X, [H | T], R) -> prepend(X, T, [[X | H] | R]).
  

  Anyway you should benchmark for your language and purposes.