4
\$\begingroup\$

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?

\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ For memoization to work is it not required that the function returns the same with no side effects for the same input arguments? I.e. you should not use it in something like remove_from_storage(5), which updates a storage count of something? \$\endgroup\$ – holroy Oct 24 '15 at 14:47
  • \$\begingroup\$ @holroy Both your questions are correct as far as I know. If you are saying my function has side effects, sure it uses BOTTLES_CRATE, but that is a constant, so no changes will happen. If like you said it were not a constant, this approach may be bad, but then just pass BOTTLES_CRATE as a tuple, inner(bottles - i, crates, tuple(BOTTLES_CRATE)). \$\endgroup\$ – Peilonrayz Oct 24 '15 at 15:13
  • \$\begingroup\$ I don't say that your function has side effects, but as I, possibly the OP or others are not so familiar with memoization I just wanted to clarify that requirement before jumping in with both feet. :-) \$\endgroup\$ – holroy Oct 24 '15 at 15:17
  • \$\begingroup\$ @holroy Your questions were confusing, they were like answers with question-marks. :P I'll update my answer about that, thank you \$\endgroup\$ – Peilonrayz Oct 24 '15 at 15:21
  • \$\begingroup\$ Adding to @Joe Wallis' answer, you may note that memoize is already a built-in and you do not need to rewrite it. In Python 3 you can do from functools import lru_cache and avoid reinventing the weel. \$\endgroup\$ – Caridorc Oct 24 '15 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.