Integer Partition Algorithm


The partition of an integer is a way of writing it as a sum of positive integers. For example, the partitions of the number 5 are:

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

Notice that changing the order of the summands will not create a different partition.

Now how do we find the number of different partitions for any integer N? There’s a way to create a generating function, but it’s quite complicated (check Wikipedia’s entry if you are interested).

An easier solution is to use an algorithm to find all the different partitions. More specifically we want to use the divide and conquer method. So first of all we need to break the problem into smaller sub-problems.

Suppose we want to find all the partitions of the number 5. We could split all the solutions into two groups: a group which uses the number 5 itself at least once, and a group that doesn’t use it. The group that uses the number 5 has only one solution: five itself. The group that doesn’t use the number five is basically the problem of finding all the ways to come up with 5 using the sub-set 1,2,3 and 4.

Now repeat the process. We can again split the solutions to our second problem into two groups: a group with all the solutions that contain the number 4, and a group that doesn’t.

There you go, we can apply this split recursively and we’ll break the problem down into many sub-problems.

Below is the algorithm. The variable sum is the sum we are trying to reach, and largestNumber is the largest number on the sub-set we have available to reach that sum.

When sum equals zero it means we just reached the sum exactly, so the function returns 1 (i.e. it just found one way to do the sum). If sum goes below zero it means the last available number was larger than what we needed, so the function returns 0. Similarly if the largest number available is zero it means we can’t reach the sum, so the function returns 0.


#include <stdio.h>

int partition(int sum, int largestNumber){
    if (largestNumber==0)
        return 0;
    if (sum==0)
        return 1;
    if (sum<0)
        return 0;

    return partition(sum,largestNumber-1)
    + partition(sum-largestNumber,largestNumber);
}

int main(){
    int sum = 100;
    int largestNumber = 99;

    printf("%dn",partition(sum,largestNumber));

return 0;
}

Notice that this algorithm re-computes solution to the same sub-problems many times (i.e., we have overlapping sub-problems). As usual, therefore, we can use dynamic programming to make it more efficient.

The above program partitioned 100 in 15 seconds. The code below reduced this time to 0.002 seconds (i.e., 2 milliseconds).


#include <stdio.h>

int table[100][100]={0};

int partition(int sum, int largestNumber){
    if (largestNumber==0)
        return 0;
    if (sum==0)
        return 1;
    if (sum<0)
        return 0;

    if (table[sum][largestNumber]!=0)
        return table[sum][largestNumber];

    table[sum][largestNumber]=partition(sum,largestNumber-1)
    + partition(sum-largestNumber,largestNumber);
    return table[sum][largestNumber];

}

int main(){
    int sum = 100;
    int largestNumber = 99;

    printf("%dn",partition(sum,largestNumber));

return 0;
}

We can also use the bottom-up dynamic programming approach. That is, we create a table where each column represents the larger number we have available, and each row represents a possible sum we want to reach. Then we initialize it with the base cases (i.e., mark a 0 on the column that represents the largest number being 0, and a 1 on the first row, which represents the sum being equal to 0).

After that we simply need to traverse the table, where each position table[i][j] will be equal to the sum of table[i][j-1] (the part where we don’t take the largest number) and table[i-j][j] (the part where we take the largest number, so the sum will be reduced by the size of the number we just took). Just be careful to check if i-j<0, cause in this case you don't add the second part (else it would give a segmentation fault). Here's the code:

#include <stdio.h>

int table[150][150];

int partition(int sum, int largestNumber){
    int i,j;

    for (i=1;i<=sum;i++){
        for (j=1;j<=largestNumber;j++){
            if (i-j<0){
                table[i][j]=table[i][j-1];
                continue;
            }
            table[i][j]=table[i][j-1]+table[i-j][j];
        }
    }

    return table[sum][largestNumber];
}

int main(){
    int sum = 100;
    int largestNumber = 99;
    int i;

    /*initialize table with base cases*/
    for (i=0;i<=sum;i++)
        table[i][0]=0;
    for (i=1;i<=largestNumber;i++)
        table[0][i]=1;

    printf("%dn",partition(sum,largestNumber));

return 0;
}
When I partitioned 900 the top-down approach took 17 milliseconds to compute, while the bottom-up one took 11 milliseconds. Both were very fast, but once you start working with huge numbers the bottom-up one is probably your best choice.

14 thoughts on “Integer Partition Algorithm

  1. Joe

    Hi Daniel. Good stuff, thank you. You should add 3+1+1 to the list at the beginning.

    Keep going on ProjectEuler! Hint your algorithm above will come in very handy.

    Reply
  2. monu

    Hai Daniel . can you provide me the source code to print the fixed size partitions of given number
    for example if n=5 and length is 4
    then
    1+1+1+2
    1+2+2+0
    1+1+3+0
    2+3+0+0
    1+4+0+0
    5+0+0+0

    Reply
  3. hamstap85

    I have already tried this in Ruby, but it is HYPER expensive. It’s the second try on a process, and for n=30, the first process took about 0.82 seconds to complete, and this one had gone for minutes before I just cancelled it. How may I submit my idea?

    Reply
  4. sekhar

    Thanks for the program. One small correction: you should add 1 to the final answer as the largest number can be equal to the number itself.

    Reply
  5. James T

    I’d rather think of this problem as the coin change problem with denominations = [1,2…n-1] and target coin size to reach as n.

    Also, a dumb q: why does passing 3,2 to the naive version of your code gives the answer 2?
    shouldn’t it be:
    3
    2+1
    1+1+1

    so 3?

    Reply
    1. aliowka

      Passing 3,2 you are restricting the largest number to be 2. Means you are going to partition 3 as a combinations of 1 and 2. That is
      1+1+1
      1+2
      So the answer is 2 combinations.

      Reply
  6. Aniket

    The example that you took for Integer Partition(Recursive Approach) i.e
    5
    4+1
    3+2
    2+2+1
    2+1+1+1
    1+1+1+1+1 , you forgot 3+1+1..Which makes the total partitions as 7 not 6..
    There should be a change in the code by adding an extra condition:
    if (sum==largestNumber)
    return 1 + partition(sum, largestNumber-1);

    Reply
  7. Aniket Sanadhya

    Your comment is awaiting moderation.
    The example that you took for Integer Partition(Recursive Approach) i.e
    5
    4+1
    3+2
    2+2+1
    2+1+1+1
    1+1+1+1+1 , you forgot 3+1+1..Which makes the total partitions as 7 not 6..
    There should be a change in the code by adding an extra condition:
    if (sum==largestNumber)
    return 1 + partition(sum, largestNumber-1);

    Reply
  8. Alexandre Mutricy

    So how would you modify the last algorithm to also save the partitions ?
    I have been trying to figure that out with no success.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *