9
\$\begingroup\$

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]
\$\endgroup\$
10
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Thanks a lot, I was thinking there must be a more efficient way to count the combinations, you found a great pattern for it \$\endgroup\$ – Vermillion Oct 12 '16 at 18:33
  • 1
    \$\begingroup\$ I really like the use of Counter instead of just assuming that the cash parameter should be a dict. It offers much more flexibility. \$\endgroup\$ – Mathias Ettinger Oct 12 '16 at 19:54
4
\$\begingroup\$

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?

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

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.