I'm calculating how many possibilities there are to fit \$n\$ identical bottles inside \$k\$ crates of various capacities.

• n = Number of bottles
• k = Number of crates
• K = List of the number of bottles each crate can fit

Each crate may be filled with any number of bottles up to \$K_i\$, including being empty.

This is an instance of the Donut Shop Problem.

Example 1

Let's say we have:

• 7 Bottles (\$n = 7\$)
• 2 Crates (\$k = 2\$)
• Crate 1 fits 3 bottles, crate 2 fits 5 bottles (\$K_1 = 3, K_2 = 5\$)

There are 2 possibilities to fit the bottles inside the crates.

Example 2

• 7 Bottles (\$n = 7\$)
• 2 Crates (\$k = 2\$)
• Crate 1 fits 2 bottles, crate 2 fits 3 bottles, crate 3 fits 4 bottles (\$K_1 = 2, K_2 = 3, K_3 = 4\$)

6 possibilities

I have a recursive solution that works fine for small integers:

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

But when I try it with \$n = 30, k= 20, K_i = i\$, it takes FOREVER, so I'm asking you: how could I improve the above code/function?

I'm calculating how many possibilities there are to fit \$n\$ identical bottles inside \$k\$ crates of various capacities.

• n = Number of bottles
• k = Number of crates
• K = List of the number of bottles each crate can fit

Each crate may be filled with any number of bottles up to \$K_i\$, including being empty.

This is an instance of the Donut Shop Problem.

Example 1

Let's say we have:

• 7 Bottles (\$n = 7\$)
• 2 Crates (\$k = 2\$)
• Crate 1 fits 3 bottles, crate 2 fits 5 bottles (\$K_1 = 3, K_2 = 5\$)

There are 2 possibilities to fit the bottles inside the crates.

Example 2

• 7 Bottles (\$n = 7\$)
• 3 Crates (\$k = 3\$)
• Crate 1 fits 2 bottles, crate 2 fits 3 bottles, crate 3 fits 4 bottles (\$K_1 = 2, K_2 = 3, K_3 = 4\$)

6 possibilities

I have a recursive solution that works fine for small integers:

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

But when I try it with \$n = 30, k= 20, K_i = i\$, it takes FOREVER, so I'm asking you: how could I improve the above code/function?

I'm calculating how many possibilities there are, to fit \$n\$ identical bottles inside \$K\$ crates of various capacities.

• n = Number of bottles
• k = Number of crates
• K = List of the number of bottles each crate can fit

Each crate may be filled with any number of bottles up to \$K_i\$, including being empty.

This is an instance of the Donut Shop Problem.

Example 1

Let's say we have:

• 7 Bottles (\$n = 7\$)
• 2 Crates (\$k = 2\$)
• Crate 1 fits 3 bottles, crate 2 fits 5 bottles (\$K_1 = 3, K_2 = 5\$)

There are 2 possibilities to fit the bottles inside the crates.

Example 2

• 7 Bottles (\$n = 7\$)
• 2 Crates (\$k = 2\$)
• Crate 1 fits 2 bottles, crate 2 fits 3 bottles, crate 3 fits 4 bottles (\$K_1 = 2, K_2 = 3, K_3 = 4\$)

6 possibilities

I have a recursive solution that works fine for small integers:

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

But when I try it with \$n = 30, k= 20, K_i = i\$, it takes FOREVER, so I'm asking you: how could I improve the above code/function?

I'm calculating how many possibilities there are to fit \$n\$ identical bottles inside \$k\$ crates of various capacities.

• n = Number of bottles
• k = Number of crates
• K = List of the number of bottles each crate can fit

Each crate may be filled with any number of bottles up to \$K_i\$, including being empty.

This is an instance of the Donut Shop Problem.

Example 1

Let's say we have:

• 7 Bottles (\$n = 7\$)
• 2 Crates (\$k = 2\$)
• Crate 1 fits 3 bottles, crate 2 fits 5 bottles (\$K_1 = 3, K_2 = 5\$)

There are 2 possibilities to fit the bottles inside the crates.

Example 2

• 7 Bottles (\$n = 7\$)
• 2 Crates (\$k = 2\$)
• Crate 1 fits 2 bottles, crate 2 fits 3 bottles, crate 3 fits 4 bottles (\$K_1 = 2, K_2 = 3, K_3 = 4\$)

6 possibilities

I have a recursive solution that works fine for small integers:

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

But when I try it with \$n = 30, k= 20, K_i = i\$, it takes FOREVER, so I'm asking you: how could I improve the above code/function?

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 doesn't need to be full, it can even be empty.

I'm calculating how many possibilities there 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 I'm asking you;

Question:

How could I improve above code/function?

I'm calculating how many possibilities there are, to fit \$n\$ identical bottles inside \$K\$ crates of various capacities.

• n = Number of bottles
• k = Number of crates
• K = List of the number of bottles each crate can fit

Each crate may be filled with any number of bottles up to \$K_i\$, including being empty.

This is an instance of the Donut Shop Problem.

Example 1

Let's say we have:

• 7 Bottles (\$n = 7\$)
• 2 Crates (\$k = 2\$)
• Crate 1 fits 3 bottles, crate 2 fits 5 bottles (\$K_1 = 3, K_2 = 5\$)

There are 2 possibilities to fit the bottles inside the crates.

Example 2

• 7 Bottles (\$n = 7\$)
• 2 Crates (\$k = 2\$)
• Crate 1 fits 2 bottles, crate 2 fits 3 bottles, crate 3 fits 4 bottles (\$K_1 = 2, K_2 = 3, K_3 = 4\$)

6 possibilities

I have a recursive solution that works fine for small integers:

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

But when I try it with \$n = 30, k= 20, K_i = i\$, it takes FOREVER, so I'm asking you: how could I improve the above code/function?