# List of all possible monetary totals from a set of cash

This code prints out a list of all the possible sums that can be made from a set of cash.

For example, say you have 2 fives and 2 tens in your wallet. With these, you can make exact change for $0,$5, $10,$15, $20,$25, and $30. import itertools cash = {1: 1, 5: 3, 10: 2} # Keys are denominations (e.g.$1 bill)
# Values are the numbers of bills (e.g. three $1 bills) totals = set() # Set of possible totals cash_list = [i for i in sorted(cash) for j in range(cash[i])] # List of all bills for r in range(len(cash_list)+1): for subset in itertools.combinations(cash_list, r): # All the bill combinations totals.add(sum(subset)) # Record the total of the bills print(sorted(list(totals))) # Print all possible totals  Output: [0, 1, 5, 6, 10, 11, 15, 16, 20, 21, 25, 26, 30, 31, 35, 36]  ## 2 Answers ### 1. Review 1. 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())  2. 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

• Thanks a lot, I was thinking there must be a more efficient way to count the combinations, you found a great pattern for it – Vermillion Oct 12 '16 at 18:33
• I really like the use of Counter instead of just assuming that the cash parameter should be a dict. It offers much more flexibility. – 301_Moved_Permanently Oct 12 '16 at 19:54

First up, I'd start by wrapping your code in a function. This will help to define what it is your expecting to be passed into your algorithm and what you're expecting back out of it. This in turn will make it easier to reuse the functionality if you decide to ask the user for the note information / read the information from a file instead.

I'd also think about the comments you're using. Generally I try to use comments to describe why something is done, not what is done. Programmers can tell what the code does by reading the code, so the why is the missing bit. This also helps to stop the comments from getting out of sync with the code if you refactor.

For example, this comment adds no extra context:

totals = set() # Set of possible totals


And this comment actually adds confusion:

cash = {1: 1, 5: 3, 10: 2} # Keys are denominations (e.g. $1 bill) # Values are the numbers of bills (e.g. three$1 bills


"(e.g. three $1 bills", where the code only shows one$1 bill. Should it be 1 or 3, is the comment right or the code?

• Good point about the comments, I'll change the example to a general n bills, instead of three – Vermillion Oct 12 '16 at 14:20