Generating the partitions of a number

Question

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.

Solution 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.

Solution 2

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]]

Solution 3

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.

Solution 4

Here's a much more long-winded way of doing it (this is what I did before I knew the term "partition", which enabled me to do a google search):

def magic_chunker (remainder, chunkSet, prevChunkSet, chunkSets):
    if remainder > 0:
        if prevChunkSet and (len(prevChunkSet) > len(chunkSet)): # counting down from previous
            # make a chunk that is one less than relevant one in the prevChunkSet
            position = len(chunkSet)
            chunk = prevChunkSet[position] - 1
            prevChunkSet = [] # clear prevChunkSet, no longer need to reference it
        else: # begins a new countdown; 
            if chunkSet and (remainder > chunkSet[-1]): # no need to do iterations any greater than last chunk in this set
                chunk = chunkSet[-1]
            else: # i.e. remainder is less than or equal to last chunk in this set
                chunk = remainder #else use the whole remainder for this chunk
        chunkSet.append(chunk)
        remainder -= chunk
        magic_chunker(remainder, chunkSet, prevChunkSet, chunkSets)
    else: #i.e. remainder==0
        chunkSets.append(list(chunkSet)) #save completed partition
        prevChunkSet = list(chunkSet)
        if chunkSet[-1] > 1: # if the finalchunk was > 1, do further recursion
            remainder = chunkSet.pop() #remove last member, and use it as remainder
            magic_chunker(remainder, chunkSet, prevChunkSet, chunkSets)
        else: # last chunk is 1
            if chunkSet[0]==1: #the partition started with 1, we know we're finished
                return chunkSets
            else: #i.e. still more chunking to go 
                # clear back to last chunk greater than 1
                while chunkSet[-1]==1:
                    remainder += chunkSet.pop()
                remainder += chunkSet.pop()
                magic_chunker(remainder, chunkSet, prevChunkSet, chunkSets)

partitions = []
magic_chunker(10, [], [], partitions)
print partitions

>> [[10], [9, 1], [8, 2], [8, 1, 1], [7, 3], [7, 2, 1], [7, 1, 1, 1], [6, 4], [6, 3, 1], [6, 2, 2], [6, 2, 1, 1], [6, 1, 1, 1, 1], [5, 5], [5, 4, 1], [5, 3, 2], [5, 3, 1, 1], [5, 2, 2, 1], [5, 2, 1, 1, 1], [5, 1, 1, 1, 1, 1], [4, 4, 2], [4, 4, 1, 1], [4, 3, 3], [4, 3, 2, 1], [4, 3, 1, 1, 1], [4, 2, 2, 2], [4, 2, 2, 1, 1], [4, 2, 1, 1, 1, 1], [4, 1, 1, 1, 1, 1, 1], [3, 3, 3, 1], [3, 3, 2, 2], [3, 3, 2, 1, 1], [3, 3, 1, 1, 1, 1], [3, 2, 2, 2, 1], [3, 2, 2, 1, 1, 1], [3, 2, 1, 1, 1, 1, 1], [3, 1, 1, 1, 1, 1, 1, 1], [2, 2, 2, 2, 2], [2, 2, 2, 2, 1, 1], [2, 2, 2, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

View more solutions

Comments

[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.

[sidgeon smythe]

No need to be so self-deprecating! Have you tested that this works? How do you call this function? Is there an example?

[johnbasil]

thanks @ShreevatsaR, yes it does work and I've now made it into a full example

[Arash Kazemi]

Please explain your answer.

[Jay]

You can't get any better than exponential, since there is an exponential number of partitions!

[sidgeon smythe]

He moved his blog; the last link is now here.

[Evgeni Nabokov]

lastPartition.length is n, right? All partition arrays have the same size.

[Evgeni Nabokov]

It seems to me that your logic is wrong. For n=6 it does not have [2,2,2], [3,3].