List of all possible monetary totals from a set of cash

Question

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]

Answer 1

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

Answer 2

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?