since im sure youre all aware of the "Real Donut Shop Problem" (https://math.stackexchange.com/questions/223345/counting-donuts). So i just start..

I have 3 Integers, all three are entered by a user. with them i need to calculate how many possible permutations they are. I already got some code, it works fine for small integers, if they get bigger, my tool runs for literally days/hours?

recursive function to calculate possible permutations:

def T(n, k, K):
if k==0: return n==0
return sum(T(n-i, k-1, K) for i in xrange(0, K[k-1]+1))

Explanation:

• n = Number of Bottles
• k = Number of crates,
• K = Maximum Number of possible Bottles one crate can fit

K is different for each crate, and doesnt need to be full, it can even be empty.

So, as you see, im calculating how many possibilies they are, to fit X given Bottles inside X given Crates, where one crate can fit a maximum of X Bottles.

Example for better Understanding: Lets say, we have:

• 7 Bottles (n)
• 2 Crates (k) -> [k1, k2]
• k1 fits 3 Bottles (K1), k2 fits 5 Bottles (K2) [k1 -> 3, k2 -> 5]

So they are 2 possibilities to fit the bottles inside the crates.

Another one:

• 7 Bottles (n)
• 3 Crates (k) -> [k1, k2, k3]
• k1 fits 2 Bottles, K2 fits 3 Bottles, K3 fits 4 Bottles

6 possibilities

Above code calculates that flawless, but when i try it with like:

Problem:

• 30 Bottles (n)
• 20 Crates (k)
• k1 -> 1 Bottle (K1), k2 -> 2 Bottles (K2), k3 -> 3 Bottles (K3), k4 -> 4 Bottles (K4).. and so on until k20 -> 20 Bottles (K20), im sure you get the idea..

It takes FOREVER, so im asking you;

Question:

how could i improve above code/function?