Dynamic Programming Part III - Partition Function

Partition Function is function to find distinct ways to sum natural numbers to a target number. Such as 4 can be partitioned to 5 distinct ways:

4
3+1
2+2
2+1+1
1+1+1+1

Consider above summation and find overlapping function, we can notice that we can deduct 1 to 4 from target number. If the result is 0, it is the solution. If result is greater than 0, we must do further deduction. And this is the formula of partition function:



Where m is maximum number to deduct, n is the remaining. Whenever n is 0, means it is a solutions. But if n is less than 0, there is no solution for remaining less than 0. We can write above function into following code:

Func<int, int, int> p = null;
p = (m, n) => 1.To(m).Sum(i => p(i, n - i));
p = p.When((m, n) => n == 0, (m, n) => 1);
p = p.When((m, n) => n < 0, (m, n) => 0);
p = p.Memoize();

We can find the partition function of 100 by using following code:

Console.WriteLine(p(100, 100));
//190569292

We can adapt above function to find partition function using a specific set of number. Such as changing £2 to any number of coins (1p, 2p, 5p, 10p, 20p, 50p, 1£, and 2£). Following is the formula.



Where s(i) is the value of a specific item in the set. And now m is the upper bound of the set. We can solve number of solutions of changing for £2 with following code:

int[] s = null;
Func<int, int, int> p = null;
p = (m, n) => 0.To(m).Sum(i => p(i, n - s[i]));
p = p.When((m, n) => n == 0, (m, n) => 1);
p = p.When((m, n) => n < 0, (m, n) => 0);
p = p.Memoize();

s = new[] { 1, 2, 5, 10, 20, 50, 100, 200 };
Console.WriteLine(p(s.Length - 1, 200));
//73682

Next, we can also find the first target number, partitioned by prime numbers, and has over 5000 solutions.

s = new Prime().TakeWhile(x => x <= 100).Cast<int>().ToArray();
Console.WriteLine(1.To(100).First(i => p(s.Length - 1, i) >= 5000));
//71

This post is the end of dynamic programming series. The challenging part of dynamic programming is to find overlapping substructure. Once you find the substructure, your computation of the functions will be extremely fast. Next post is about number which is real number.