1. Review
The data structure cash
is a map from denomination to the count of the bills in that denomination. This is a representation of a multiset, and it's a good idea here to use the built-in collections.Counter
:
from collections import Counter
cash = Counter({1: 1, 5: 3, 10: 2})
Now you can replace this line:
cash_list = [i for i in sorted(cash) for j in range(cash[i])]
with a call to the Counter.elements
method:
cash_list = list(cash.elements())
The code is not organized into functions. This makes it hard to test and hard to measure the performance. It would be better to write something like this:
from collections import Counter
from itertools import combinations
def change(cash):
"""Given a map from denomination to the count of bills in that
denomination, return the set of values that can be made using a
subset of the bills.
"""
totals = set() # Set of possible totals
cash_list = list(Counter(cash).elements()) # List of all bills
for r in range(len(cash_list)+1):
for subset in combinations(cash_list, r):
totals.add(sum(subset))
return totals
Now we can easily test it:
>>> change({1:1, 2:1, 4:1, 8:1}) == set(range(16))
True
and measure its performance:
>>> from timeit import timeit
>>> timeit(lambda:change({1:20}), number=1)
0.6443959611933678
2. Performance
The algorithm loops over all subsets of bills. But this doesn't take advantage of the fact that bills of the same denomination are indistinguishable. For example, we know that
change({1:25}) == set(range(26))
since if you have twenty-five $1 bills, you can make change for all dollar amounts from $0 to $25. But this calculation, that should be trivial, takes a very long time:
>>> timeit(lambda:change({1:25}), number=1)
22.855976961087435
And good luck waiting for, say, change({1:100})
to finish running. So we can improve the performance in these cases by taking advantage of the fact that if have \$n\$ bills of denomination \$d\$, the possible values are \$0, d, 2d, \ldots, nd\$, that is, range(0, (n + 1) * d, d)
. Using itertools.product
we can write it like this:
from collections import Counter
from itertools import product
def change2(cash):
"""Given a map from denomination to the count of bills in that
denomination, return the set of values that can be made using a
subset of the bills.
"""
ranges = [range(0, (n + 1) * d, d) for d, n in Counter(cash).items()]
return set(map(sum, product(*ranges)))
This is slightly slower than the original code in cases where all the denominations are different:
>>> timeit(lambda:change({2**i:1 for i in range(20)}), number=1)
0.9978475249372423
>>> timeit(lambda:change2({2**i:1 for i in range(20)}), number=1)
1.0107885741163045
but it is massively faster in cases where there are many bills of a denomination:
>>> timeit(lambda:change2({1:25}), number=1)
0.000085500068962574