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)

This more math related may be ask on math version of this site. If it was me I would do it for 9 boxes and then multiplied result by 10 but my math is not that good. — estinamir
– estinamir, Commented Mar 23, 2020 at 15:37
This can be solved with binomial coefficient, it is built in some py modules: stackoverflow.com/questions/26560726/… — Guy_g23
– Guy_g23, Commented Mar 23, 2020 at 15:40
@Guy_g23 I don't think a binomial coefficient would solve this but happy to change my mind if you show that it can. — Jacques Gaudin
– Jacques Gaudin, Commented Mar 23, 2020 at 19:17
@JacquesGaudin This is a combinatorics question given that any positive and discrete amount of apples can be placed in one box. Check this answer: math.stackexchange.com/a/58756 — Guy_g23
– Guy_g23, Commented Mar 23, 2020 at 19:24
@Guy_g23 Ok I think it depends whether the boxes are identifiable or not. en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29 — Jacques Gaudin
– Jacques Gaudin, Commented Mar 23, 2020 at 19:37

Jacques Gaudin · Accepted Answer · 2020-03-23 19:24:12Z

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).

Collectives™ on Stack Overflow

Python - Calculating total possibilities using recursion

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related