Counting ways to fit bottles in crates

Question

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?

Answer 1

You should 'spread out' your code more, k==0 kinda looks like a variable, and if k==0: return n==0 doesn't really look like an if statement at first.

Single letter variable names are bad, amount_bottles is better then n. You could even use bottles and it would still be better.

T is not an allowed name for a function according to PEP8 Python's style guide. Capital letters are only used in constants, and classes.

As for your performance concern, I would recommend using memoization in a wrapper. memoization remembers output, and so you re-use the output rather then re-find it. It's really good in recursive functions.

def memoize(fn):
    outputs = {}
    def inner(*args):
        try:
            return outputs[args]
        except KeyError:
            outputs[args] = fn(*args)
            return outputs[args]
    return inner

def permutations(bottles, crates, BOTTLES_CRATE):
    @memoize
    def inner(bottles, crates):
        if crates == 0:
            return bottles == 0
        crates -= 1
        return sum(
            inner(bottles - i, crates)
            for i in xrange(BOTTLES_CRATE[crates] + 1)
        )
    return inner(bottles, crates)

print(permutations(30, 20, range(1, 21)))

This took under a second to get 6209623185136.

---

Just to note, memoization requires no side effects to happen. So if you use an outside variable then that can break the memoization.

For example, if we were to memoize addition of a number plus a global variable, it is prone to breakage.

inc = 4

@memoize
def add(num):
    return num + inc

add(4) # 8
inc = 0
add(4) # 8
add(0) # 0

If you were to want to expand on your above code, and you make BOTTLES_CRATE a variable, then you would have to pass BOTTLES_CRATE via the memoizer too. Just like we should inc in the above.

@memoize
def add(a, b):
    return a + b

add(4, 4) # 8
add(4, 0) # 4

As I use a dictionary to store the arguments, you will need to cast BOTTLES_CRATE to a hash-able type, e.g. a tuple. This may lead to a non-transparent solution, where you can just add @memoize.

Another bad use-case is if add 'returns' from it's internals to another variable.

list_ = []

@memoize
def push(num):
    list_.append(num)

push(2) # list_ == [2]
push(2) # list_ == [2]

And so if there are possible side effects, you may want to chose a different method in future.