Python - Calculating total possibilities using recursion

Question

I am trying to find the total possibilities of how to place 90 apples in 90 boxes. Any amount of apples can be placed in one box (0 to 90 apples), but all apples have to be placed into boxes. I used recursion but it took way too much time to complete the calculation. I was only able to test my code with small amounts of apples and boxes. Could anyone help me on reduce the time complexity of my code? Thanks in advance.

import math

boxes = 3
apples = 3

def possibilities(apples, boxes):
    if apples == 0:
        return 1
    if boxes == 0:
        return 0
    start_point = 0 if boxes > 1 else math.floor(apples/boxes)

    p = 0
    for n in range(start_point, apples+1):
        p += possibilities(apples-n, boxes-1)
    return p

t = possibilities(apples,boxes)
print(t)

user_1388292 · Answer

The way I see it, the problem consists in finding the number of sorted list of max 90 elements which have a sum equal to 90.

There is a concept which is quite close to this and we call it the partitions of a number.

For example, the partitions of 4 are [4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1].

After a bit of research I found this article which is relevant to your problem.

As explained in there, the recursion method results in a very long calculation for large numbers, but...

A much more efficient approach is via an approach called dynamic programming. Here we compute a function psum(n,k), which is the total number of n-partitions with largest component of k or smaller. At any given stage we will have computed the values of psum(1,k), psum(2,k), psum(3,k), ..., psum(n,k) for some fixed k. Given this vector of n values we compute the values for k+1 as follows:

psum(i,k+1) = psum(i,k) + p(i,k) for any value i

But recall that p(i,k) = Σj p(i-k,j) = psum(i-k,k)

So psum(i,k+1) = psum(i,k) + psum(i-k,k)

So with a little care we can reuse the vector of values and compute the values of psum(i,k) in a rolling value for successively greater values of k. Finally, we have a vector whose values are psum(i,n). The value psum(n,n) is the desired value p(n). As an additional benefit we see that we have simultaneously computed the values of p(1), p(2), ..., p(n).

Basically, if you keep the intermediate values in a list and use the recurrence presented in the article,

psum(i,k+1) = psum(i,k) + psum(i-k,k)

you can use the following function:

def partitionp(n):
    partpsum = [1] * (n + 1)
    for i in range(2, n + 1):
        for j in range(i, n + 1):
            partpsum[j] += partpsum[j - i]
    return partpsum[n]

At each iteration of the outer for loop, the list partpsum contains all the value psum(1,k), psum(2,k), psum(3,k), ..., psum(n,k). At the end of the iteration, you only need to return psum(n,n).

Python - Calculating total possibilities using recursion

1 Answers