15

Counting the Ways You Can Count Change

Money often costs too much.

—Ralph Waldo Emerson

Programming constructs and algorithmic paradigms covered in this puzzle: Recursive generation of combinations.

You have piles of money. In fact, you have piles of almost every kind of dollar bill that was ever printed. This includes $1, $2, $5, $10, $20, $50, and $100 bills.¹

You owe your friend $6. Your friend knows you have piles of cash, and asks if you know how many different ways you can pay using different denominations of bills. You think for a while, collecting different bills, checking what they add up to, and figure out that there are only five different ways:

• $1, $1, $1, $1, $1, $1
• $1, $1, $1, $1, $2
• $1, $1, $2, $2
• $1, $5
• $2, $2, $2

(Although each bill has a different serial number, you view two bills as identical if they have the same denomination.)

All of a sudden you realize you actually owe your friend $16, remembering the $20 dinner you had together recently, after which you couldn’t pay your share because you had forgotten your wallet.

What are all the different ways you can pay your friend $16? How many ways are there?

Recursive Bill Selection

We will explore different ways of selecting bills, keeping track of the total value of the bills selected. As long as the total value is less than our target value, we will add more bills. If we exceed the target value, we simply discard the solution. If we get the exact target total, we print (or store) the solution and keep going. Remember, we want all possible solutions that exactly reach the target value.

The easiest way to implement such an exploration is to use recursion—which probably does not surprise you by now. Here’s code that recursively enumerates possible solutions.

  1.      def makeChange(bills, target, sol = []):

  2.                if sum(sol) == target:

  3.                       print (sol)

  4.                       return

  5.                if sum(sol) > target:

  6.                            return

  7.                for bill in bills:

  8.                        newSol = sol[:]

  9.                        newSol.append(bill)

10.                        makeChange(bills, target, newSol)

11.                return

The first argument to the function is a list of bill denominations in bills, for example, [1, 2, 5]. The second argument is the target value, and the third is the solution sol, which is a list of chosen bill denominations. Lines 2–4 correspond to a base case where we discover a solution and print it. In this particular implementation, we are not storing or counting possible solutions, merely printing them out as we discover them.

Lines 5–6 are another base case, where we have exceeded the target value. We simply discard this non-solution. There is no reason to pay your friend more than you owe.

Lines 7–10 explore the solution space. For each denomination listed in bills, we copy the current solution to a list newSol, and add a bill of that denomination to it. Then we recursively call makeChange with the longer list newSol.

Since we are iterating over different bill denominations, we need to make a copy of sol in newSol (line 8). Why? Suppose we did not make a copy of sol in newSol, and just used sol everywhere in the code. Let’s say bills = [1, 2, 5] and we are exploring solutions with sol = [1]. We add 1 to sol to get sol = [1, 1]. We go ahead and make recursive calls with this sol, and each call adds to the list sol. Once these calls return—some solutions may have been found, and non-solutions discarded—we go to the next iteration of the loop. We would like for sol to be [1], so we can add 2 to it and explore solutions with sol = [1, 2]. Unfortunately, sol could be a long list (depending on the target value) since we have not removed any elements from it. Adding another bill to this list will likely mean exceeding the target value. Copying sol to newSol ensures that we properly explore the entire space.

Suppose we run:

bills = [1, 2, 5]

makeChange(bills, 6)

This outputs:

[1, 1, 1, 1, 1, 1]

[1, 1, 1, 1, 2]

[1, 1, 1, 2, 1]

[1, 1, 2, 1, 1]

[1, 1, 2, 2]

[1, 2, 1, 1, 1]

[1, 2, 1, 2]

[1, 2, 2, 1]

[1, 5]

[2, 1, 1, 1, 1]

[2, 1, 1, 2]

[2, 1, 2, 1]

[2, 2, 1, 1]

[2, 2, 2]

[5, 1]

There is a problem here. The program is repeating solutions and produces 15 lines of output. It seems to think that the order of the bills matters—that four $1 bills, then a $2 bill, is different from three $1 bills, then a $2 bill, then a $1 bill. It does realize that bills of the same denomination are identical, and does not generate 6! = 720 different [1, 1, 1, 1, 1, 1] solutions, thank goodness!

Eliminating Repetition

How can we eliminate this repetition of solutions? We can use the natural ordering of the bill denominations to generate solutions of a particular form. We won’t generate any solution of the form [a, b] or [a, b, c] where b < a or c < b or c < a. Each solution will correspond to a possibly different but always nondecreasing order of denomination. Certainly, we need to allow solutions [a, b, c], where b ≥ a, or c ≥ b, or c ≥ b ≥ a. But we will preclude a solution like [1, 1, 1, 2, 1] because it is not a nondecreasing sequence, and similarly, [5, 1]. The allowed solutions for these two cases will be [1, 1, 1, 1, 2] and [1, 5].

We therefore make a small, subtle modification to makeChange. We add an argument that corresponds to the highest denomination that has been generated thus far. In recursive exploration, we will only add denominations that are equal to or greater than the highest denomination added thus far, and not ones that are lower. On our initial call to the modified procedure, we will set this new argument to the lowest-denomination bill, which in our examples is $1. This means we can keep adding $1 bills, but if we ever add a $2 bill, we cannot go back to adding a $1 bill.

This algorithmic change is embodied in the function makeSmartChange below.

  1..      def makeSmartChange(bills, target, highest, sol = []):

  2.                if sum(sol) == target:

  3.                         print (sol)

  4.                         return

  5.                if sum(sol) > target:

  6.                            return

  7.                for bill in bills:

  8.                         if bill >= highest:

  9.                                 newSol = sol[:]

10.                                 newSol.append(bill)

11.                                 makeSmartChange(bills, target, bill, newSol)

12.                return

Note the additional highest argument that we discussed (line 1). Exactly one line has been added to makeChange—line 8. When we generate a new solution, we make sure that the bill that is appended has a value greater than or equal to highest. We also have to change the recursive call on line 11 since we have added an argument to the function. The argument has to be bill—we can’t leave it as highest, because bill may be greater than highest as we go through the for loop (lines 7–11). But once we have added bill >= highest and made a recursive call, inside that recursive call, highest will equal bill.

This modification fixes the problem with makeChange. If we run:

bills = [1, 2, 5]

makeSmartChange(bills, 6, 1)

The program produces:

[1, 1, 1, 1, 1, 1]

[1, 1, 1, 1, 2]

[1, 1, 2, 2]

[1, 5]

[2, 2, 2]

This set of solutions you knew already. But if we run:

bills2 = [1, 2, 5, 10]

makeSmartChange(bills2, 16, 1)

We get twenty-five different ways of counting $16, namely:

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 2, 2, 5]

[1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

[1, 1, 1, 1, 1, 1, 5, 5]

[1, 1, 1, 1, 1, 1, 10]

[1, 1, 1, 1, 1, 2, 2, 2, 5]

[1, 1, 1, 1, 2, 2, 2, 2, 2, 2]

[1, 1, 1, 1, 2, 5, 5]

[1, 1, 1, 1, 2, 10]

[1, 1, 1, 2, 2, 2, 2, 5]

[1, 1, 2, 2, 2, 2, 2, 2, 2]

[1, 1, 2, 2, 5, 5]

[1, 1, 2, 2, 10]

[1, 2, 2, 2, 2, 2, 5]

[1, 5, 5, 5]

[1, 5, 10]

[2, 2, 2, 2, 2, 2, 2, 2]

[2, 2, 2, 5, 5]

[2, 2, 2, 10]

Nice! Be careful when running this code—the number of solutions explodes as the target value increases, especially if you have low-denomination bills.

Making Change with the Fewest Bills

Suppose you are interested in using the fewest possible bills to pay your friend. The output produced by our code clearly has that information in it. In the $16 example, for instance, you pay your friend using three bills: $1, $5, and $10.

Your first impulse, understandably, may be to try a greedy algorithm. The greedy algorithm would pick the highest-denomination bill that is less than the money owed, lower the target appropriately, and repeat the process. It certainly works for the $16 case: $10 is picked first, then $5, then $1. What if you lived in Simbuktu, where there is an $8 bill? The optimal solution would be two $8 bills, and the greedy algorithm will miss that. Of course, makeSmartChange will produce the two $8 bills solution as one of the valid ones.

One way of always finding the solution with the fewest bills is to run makeSmartChange and pick the minimum cardinality solution during the enumerative process. Exercise 3 asks you do this.

Exercises

Exercise 1:    Modify makeSmartChange so that rather than printing each solution, it merely counts the number of distinct solutions and returns the count. You can use a global variable count that counts solutions across recursive calls. There are more efficient ways of simply counting the number of possible solutions²—your job here is to modify the given code.

Puzzle Exercise 2:    Suppose you are not as rich as we made you out to be, and you only have a limited number of bills of different denominations. For example, the representation of your stash is:

yourMoney = [(1, 11), (2, 7), (5, 9), (10, 10), (20, 4)]

where the first entry in each tuple in the list is the bill denomination, and the second entry is the number of bills you have of that denomination. In the above example, you have eleven $1 bills and four $20 bills, for instance. Modify the program so it only outputs solutions that you are capable of constructing with your somewhat limited amount of money.

An easy method is to generate all the solutions as before, and discard—without printing—the ones that violate the numeric constraints. We encourage you to follow the more elegant and efficient method of discarding illegal partial solutions during the recursive search. Illegal partial solutions are less than the target value, but violate one or more numeric constraints.

If you run:

money = [(1, 3), (2, 3), (5, 1)]

makeSmartChange(money, 6, 1)

It should produce the three solutions below:

[1, 1, 2, 2]

[1, 5]

[2, 2, 2]

While there are three $1 bills, we cannot produce $6 (the target) using all three of them, so the solutions use either two or one $1 bills.

Exercise 3:    Since a greedy algorithm doesn’t produce the fewest number of bills that meet the target value, modify your code from exercise 2 to return one solution with the fewest bills of any denomination used. Again, do not store or print all possible solutions. Rather, just store the current best solution found, corresponding to the fewest bills, and update it during recursive execution as appropriate. Note that you will have a nontrivial best solution only after finding a first solution that meets the target value.

We’ll explore a way of making the above strategy significantly more efficient in exercise 4 of puzzle 18.

Notes

1. Sadly, you don’t have $3 bills, which haven’t been printed since about 1800, but the rest of your collection keeps you happy.

2. Arguably, the title of puzzle 15 should have been “Enumerating the Ways You Can Count Change.” See exercise 5, puzzle 18 for the real counting puzzle.