# Algorithm to partition a number

Given a positive integer X, how can one partition it into N parts, each between A and B where A <= B are also positive integers? That is, write

X = X_1 + X_2 + ... + X_N

where A <= X_i <= B and the order of the X_is doesn't matter?

## Answers

Here is a python solution to this problem, This is quite un-optimised but I have tried to keep it as simple as I can to demonstrate an iterative method of solving this problem.

The results of this method will commonly be a list of max values and min values with maybe 1 or 2 values inbetween. Because of this, there is a slight optimisation in there, (using abs) which will prevent the iterator constantly trying to find min values counting down from max and vice versa.

There are recursive ways of doing this that look far more elegant, but this will get the job done and hopefully give you an insite into a better solution.

SCRIPT:

# iterative approach in-case the number of partitians is particularly large def splitter(value, partitians, min_range, max_range, part_values): # lower bound used to determine if the solution is within reach lower_bound = 0 # upper bound used to determine if the solution is within reach upper_bound = 0 # upper_range used as upper limit for the iterator upper_range = 0 # lower range used as lower limit for the iterator lower_range = 0 # interval will be + or - interval = 0 while value > 0: partitians -= 1 lower_bound = min_range*(partitians) upper_bound = max_range*(partitians) # if the value is more likely at the upper bound start from there if abs(lower_bound - value) < abs(upper_bound - value): upper_range = max_range lower_range = min_range-1 interval = -1 # if the value is more likely at the lower bound start from there else: upper_range = min_range lower_range = max_range+1 interval = 1 for i in range(upper_range, lower_range, interval): # make sure what we are doing won't break solution if lower_bound <= value-i and upper_bound >= value-i: part_values.append(i) value -= i break return part_values def partitioner(value, partitians, min_range, max_range): if min_range*partitians <= value and max_range*partitians >= value: return splitter(value, partitians, min_range, max_range, []) else: print ("this is impossible to solve") def main(): print(partitioner(9800, 1000, 2, 100))

The basic idea behind this script is that the value needs to fall between min*parts and max*parts, for each step of the solution, if we always achieve this goal, we will eventually end up at min < value < max for parts == 1, so if we constantly take away from the value, and keep it within this min < value < max range we will always find the result if it is possable.

For this code's example, it will basically always take away either max or min depending on which bound the value is closer to, untill some non min or max value is left over as remainder.

If you want to know the **number of ways** to do this, then you can use generating functions.

Essentially, you are interested in integer partitions. An integer partition of X is a way to write X as a sum of positive integers. Let p(n) be the number of integer partitions of n. For example, if n=5 then p(n)=7 corresponding to the partitions:

5 4,1 3,2 3,1,1 2,2,1 2,1,1,1 1,1,1,1,1

The the generating function for p(n) is

sum_{n >= 0} p(n) z^n = Prod_{i >= 1} ( 1 / (1 - z^i) )

* What does this do for you?* By expanding the right hand side and taking the coefficient of z^n you can recover p(n). Don't worry that the product is infinite since you'll only ever be taking finitely many terms to compute p(n). In fact, if that's all you want, then just truncate the product and stop at i=n.

* Why does this work?* Remember that

1 / (1 - z^i) = 1 + z^i + z^{2i} + z^{3i} + ...

So the coefficient of z^n is the number of ways to write

n = 1*a_1 + 2*a_2 + 3*a_3 +...

where now I'm thinking of a_i as the number of times i appears in the partition of n.

* How does this generalize?* Easily, as it turns out. From the description above, if you only want the parts of the partition to be in a given set A, then instead of taking the product over all i >= 1, take the product over only i in A. Let p_A(n) be the number of integer partitions of n whose parts come from the set A. Then

sum_{n >= 0} p_A(n) z^n = Prod_{i in A} ( 1 / (1 - z^i) )

Again, taking the coefficient of z^n in this expansion solves your problem. But we can go further and track the **number of parts** of the partition. To do this, add in another place holder q to keep track of how many parts we're using. Let p_A(n,k) be the number of integer partitions of n into k parts where the parts come from the set A. Then

sum_{n >= 0} sum_{k >= 0} p_A(n,k) q^k z^n = Prod_{i in A} ( 1 / (1 - q*z^i) )

so taking the coefficient of q^k z^n gives the number of integer partitions of n into k parts where the parts come from the set A.

* How can you code this?* The generating function approach actually gives you an algorithm for generating all of the solutions to the problem as well as a way to uniformly sample from the set of solutions. Once n and k are chosen, the product on the right is finite.