Algotree > Algorithms > Dynamic Programming > Integer Partitioning Problem

Integer Partitioning Problem

The integer partitioning programming problem is described as below
Given.
a) Integer to be partitioned. Say an integer 4 is to be partitioned.
b) Set of available integers for partitioning. Assumption is that, we have a set of infinite integer values [ 2, 4 ]
Goal is to find the number of ways of partitioning a bigger integer with smaller integer values.

Example: If an integer of value 4 is to be partitioned with smaller integers of values [ 1, 2, 3 ] we have 4 ways
a) 4 = 1 + 1 + 1 + 1
b) 4 = 1 + 1 + 2
c) 4 = 2 + 2
d) 4 = 1 + 3
Thus we have 4 ways.

Recurrence relation

Base cases:

If an integer 0 is to be partitioned, there is always 1 way of partitioning it using any number of integers. Thus,
Partitions (number_of_integers, bigger_integer) = 1; when the integer to be partitioned is 0
If no (zero) integers are available for making partitions, there is no way of partitioning an integer value greater than 0. Thus,
Partitions (number_of_integers, bigger_integer, values) = 0; when number_of_integers equals 0 and bigger_integer > 0.

Try partitioning the bigger integer using a chosen integer from the available set

Note:
a) When the chosen integer from the set is not included for making partitions, the number_of_integers is reduced by 1.
b) When the chosen integer from the set is to be included for making partitions, the bigger integer value is reduced by the value of the chosen integer.

Thus we have the below recurrence equation,
Partition (number_of_integers, bigger_integer, values) =
Partition (number_of_integers - 1, bigger_integer, values) +
Partition (number_of_integers, bigger_integer - value [ number_of_integers - 1 ], values);

Note:
If the current integer is included for making partitions, then the value of the bigger integer is reduced to bigger_integer - denominations [ number_of_integers - 1 ]

Dynamic programming approach

Base case values

Note: An integer 0 is included in the set of available integers for partitioning for generating the base cases.

Partition integer	Using Integers	Ways	Hint
0	0	1 way ()	Integer 0 can be obtained using integer 0 by choosing integer 0.
0	0, 1	1 way (0)	Integer 0 can be obtained using integers ( 0, 1 ) by choosing integer 0.
0	0, 1, 2	1 way (0)	Integer 0 can be obtained using integers ( 0, 1, 2 ) by choosing integer 0.
0	0, 1, 2, 3	1 way (0)	Integer 0 can be obtained using integers ( 0, 1, 2, 3 ) by choosing integer 0.
1	0	0 ways ()	Integer 1 cannot be obtained using integer 0.
2	0	0 ways ()	Integer 2 cannot be obtained using integer 0.
3	0	0 ways ()	Integer 3 cannot be obtained using integer 0.
4	0	0 ways ()	Integer 4 cannot be obtained using integer 0.

Integer_Partition

Example:
Consider partitioning integer 4. Available integers for making partitions [ 1, 2, 3 ].
i.e Filling value in table [ 3 ] [ 4 ]

We get the following cases:
Case a) Integer 3 is not chosen i.e only integers of value 0, 1 and 2 are available for making partitions.
Case b) Integer 3 is chosen from the set of available integers for including in the partition.

From the recurrence equation
Partition ( number_of_integers, bigger_integer, values ) =
Partition ( number_of_integers - 1, bigger_integer, values ) +
Partition ( number_of_integers, bigger_integer - value [ number_of_integers - 1 ], values )

Thus we get,
Partition [ 3 ] [ 4 ] = Partition [ 2 ] [ 4 ] + Partition [ 3 ] [ 4 - 3 ]
Partition [ 3 ] [ 4 ] = Partition [ 2 ] [ 4 ] + Partition [ 3 ] [ 1 ]
From the DP table,
Partition [ 3 ] [ 4 ] = 3 + 1 = 4 ways

Note:
Partition [ 2 ] [ 4 ] indicate that only 2 smaller integers i.e ( 1, 2 ) are available for partitioning integer 4.
Partition [ 2 ] [ 4 ] = 3 ways i.e [ ( 1, 1, 1, 1 ), ( 1, 1, 2 ), ( 2, 2 ) ]
Partition [ 3 ] [ 1 ] indicate that 3 smaller integers i.e ( 1, 2, 3 ) are available for partitioning integer 1.
Partition [ 3 ] [ 1 ] = 1 way i.e [ ( 1, 1, 1 ) ]

Time Complexity: O ( n * m ), where n is the bigger integer to be partitioned and m is the number of smaller integers to be used for partitioning.

Integer partitioning problem implementation

from typing import List # For annotations

def GetPartitions (numset : List[int], biggernum : int) :

    size_numset = len(numset)
    dptable = [0] * (size_numset+1)

    for r in range (size_numset+1) :
        dptable[r] = [0] * (biggernum+1)

    # Number 0 can be obtained with 0 smaller numbers i.e 1 way 
    dptable[0][0] = 1 

    # Numbers greater that 0 cannot be obtained with number 0
    for c in range (1, biggernum+1) :
        dptable[0][c] = 0 

    # Number 0 can be obtained with any number i.e we do not include any number from the set 
    for r in range (1, size_numset+1) :
        dptable[r][0] = 1 

    for r in range (1, size_numset+1) :
        for c in range (1, biggernum+1) :
            if (c >= numset[r-1]) : 
               dptable[r][c] = dptable[r-1][c] + dptable[r][c-numset[r-1]]
            else :
               dptable[r][c] = dptable[r-1][c]

    return dptable[size_numset][biggernum]

num = 4 
numset = [ 1, 2, 3 ] # Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3)
print(GetPartitions(numset, num))

num = 6 
numset = [ 2, 3, 4 ] # Three ways : (2,2,2) (2,4) (3,3) 
print(GetPartitions(numset, num))

num = 10
numset = [ 2, 5, 8, 9, 10 ] # Four ways : (2,2,2,2,2) (2,8) (5,5) (10) 
print(GetPartitions(numset, num))

num = 10
numset = [ 8, 9, 10 ] # One way : (10) 
print(GetPartitions(numset, num))

Output

#include<iostream>
#include<vector>

using namespace std;

int GetPartitions (vector<int>& numset, int biggernum) {

    int size_numset = numset.size();
    int dptable[size_numset+1][biggernum+1];

    // Number 0 can be obtained with 0 smaller numbers i.e 1 way
    dptable[0][0] = 1;

    // Numbers greater that 0 cannot be obtained with number 0
    for (int n=1; n<=biggernum; n++) {
        dptable[0][n] = 0;
    }

    // Number 0 can be obtained with any number i.e we do not include any number from the set
    for (int r=1; r<=size_numset; r++) {
        dptable[r][0] = 1;
    }

    for (int r=1; r<=size_numset; r++) {
        for (int c=1; c<=biggernum; c++) {
            if (c >= numset[r-1]) {
               // Exclude the last number in the numset + Include last number in the numset
               dptable[r][c] = dptable[r-1][c] + dptable[r][c-numset[r-1]];
            } else {
               // Exclude the last number in the numset as it is bigger in value
               dptable[r][c] = dptable[r-1][c];
            }
        }
    }

    return dptable[size_numset][biggernum];
}

int main() {

    int num = 4;
    vector<int> set_1 = { 1, 2, 3 }; /* Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3) */
    cout << GetPartitions(set_1, num) << endl;

    num = 6;
    vector<int> set_2 = { 2, 3, 4 }; /* Three ways : (2,2,2) (2,4) (3,3) */
    cout << GetPartitions(set_2, num) << endl;

    num = 10;
    vector<int> set_3 = { 2, 5, 8, 9, 10 }; /* Four ways : (2,2,2,2,2) (2,8) (5,5) (10) */
    cout << GetPartitions(set_3, num) << endl;

    return 0;
}

Output

4
3
4