Making change

Consider the classic problem: How many ways can one make change for one dollar using half-dollars, quarters, dimes, nickels, and pennies? Or more generally, how many ways can one make change for a given amount using arbitrary (positive integer) denominations?

This post chronicles a series of incremental improvements to solutions to this problem. In the first section, we attack the problem with dynamic programming in Python, and we’re able to count the ways to change quite large amounts of money (eventually up to about $100M for the given set of five coins). The second section explores a nice method for deriving closed form solutions, due to Lee Newberg, and the third is a synthesis of the previous two, automating the closed form derivation in the general setting.

1. From 1 to 100,000,000

It’s not hard to produce a recursive function definition which computes the answer to the coin problem. To count all the ways of making change, we just need to condition on whether or not at least one coin of the first denomination will be used (and then add these counts together). If one will be used, then we must change the original amount minus the first denomination. If not, then we must change the whole original amount, but with one fewer denomination. In either case, we’ve made progress toward obvious base cases, so the recursion will terminate.

def make_change(amt, denoms):
    if amt < 0:     return 0
    if amt == 0:    return 1
    if not denoms:  return 0
    return make_change(amt-denoms[0], denoms) + make_change(amt, denoms[1:])


This function is sufficient for changing a dollar as originally described: make_change(100, (50,25,10,5,1)) quickly evaluates to 292.

Experimentation shows that this function really starts slowing down around five dollars, which is unacceptable. If d is the number of denominations, then the number of recursive calls that make_change must make above satisfies a recurrence something like

f(A, d) = f(A-1, d) + f(A, d-1).

Note that binomial coefficients satisfy the similar recurrence,

f(A, d) = f(A-1, d) + f(A-1, d-1).

so that the running time of make_change should grow at least as fast (up to adjustment for base cases). In short, for d=5 as above, the runtime of make_change seems to be proportional to A**4.

The easiest way to transform the above into an O(A*d)-time algorithm is memoization. Essentially, memoization transforms a (pure) function into a lookup table whose entries are evaluated lazily, in that any entry is evaluated at most once, and only if that entry is needed.

The coin changing problem has the "optimal substructure" property: a solution to a problem instance of size (A,d) can easily (i.e. in constant time) be reconstructed from solutions to all smaller subproblems. Since a problem instance of size (A,d) has only O(A*d) subproblems, the memoized version runs in O(A*d) time (and space), assuming constant-time table operations.

The easiest way to handle memoization in Python is to define the higher-order function

def memo(f):
    cache = {}
    def _f(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return _f

and to set make_change = memo(make_change) (or precede the definition of make_change with @memo, Python's syntactic sugar for such "decorators").1

By increasing Python's recursion limit (sys.setrecursionlimit), we're able to change reasonably large amounts of money before running out of memory. On my modest machine (2GB RAM), this happens a little after $5000 (with 41682501983425001 ways).

Memory usage can be eased somewhat by building the lookup table inside a loop rather than with function calls, but the table is still of size proportional to A*d. A better approach taking "only" O(A) space is to build a list/array of the number of ways to make a cents for each a < A and to add the d coins in one at a time.2

But the issue is still that we run out of memory before time constraints become noticeable (now changing $100K in 10 seconds, but crashing for $1M).

To really bring down space usage, just note that the recursion only requires bounded look-backs. That is, if m is the size of the largest denomination, then to solve the problem at (A, d), we only need to look back as far as (A-m, d) (and (A, d-1)); the rest of the table can be "forgotten". This brings space usage down to O(d*m), independent of A.

The rewrite looks like this.

With the memory problem solved, I ran the above overnight and and got data for powers of 10 up to $100M, with denoms = (50,25,10,5,1) as usual.3

1:     292
10:    801451
100:   6794128501
1K:    66793412685001
10K:   666793341266850001
100K:  6666793334126668500001
1M:    66666793333412666685000001
10M:   666666793333341266666850000001
100M:  6666666793333334126666668500000001

Starting at $100, a clear pattern emerges. This was actually the first indication to me that there might be a nice closed form solution to the problem at hand with the specified denominations, at least for whole dollar amounts. Scaling the input by 10 scales the output by roughly 10000, suggesting a quartic relation between the two. Low-degree polynomial interpolation is a fairly straightforward linear algebra problem, and it's one that Wolfram Alpha can already solve, so I felt no need to reinvent the wheel here. Given 4+1 arbitrary data points from the table above, Wolfram Alpha suggests

\displaystyle 1+\frac{55n+238n^2+380n^3+200n^4}{3}.

This agrees with the other data points in my table, and with a few other arbitrarily chosen whole dollar amounts (e.g. 9384) I tested against.

At this point, I'm quite confident that I've got the closed form solution in hand. I decided to consult the internet, and I was pleased with what I found.

2. To infinity

The really efficient algorithm is of course to just evaluate a closed form solution. The content for this section is derived from an argument by Lee Newberg in a guest post to Frank Morgan's math chat. In the post, Newberg solves the problem of making change for {n} whole dollars using the denominations 1, 5, 10, 25, 50, and the 100-cent coin/bill. In retrospect, this is probably the more reasonable problem to consider (at least for large {n}), but it's not the one I set out to solve, and adapting Newberg's 6-denomination approach to the 5-denomination version at hand forces me to work through the details omitted for brevity in his writeup.

Newberg's solution is organized around generating functions: formal power series whose coefficents relate to whatever problem we're trying to solve. While they are not strictly necessary here, effectively using generating functions seems like a skill worth developing.

The simplest example I know of a generating function in a combinatorial argument is

\displaystyle (1+x)^m\ =\ \sum_{n=0}^m{m\choose n}x^n.

Before simplification, each of the {2^m} monomial terms represented in the expansion of {(1+x)^m} corresponds to a way of choosing a subset of {\{1,2,\ldots,m\}} and "tagging" the chosen elements with {x} and the others with {1}. Collecting like terms (corresponding to sets of the same size), we see that binomial coefficients are the same thing as "{m} choose {n}", and insights about one are insights about the other.

In similar fashion, the ways to make {n} cents out of denominations 1, 5, 10, 25, and 50 correspond exactly to the ways to choose a multiple of each denomination such that the sum is {n}. Thus this number is equal to the {n}-th coefficient in

\displaystyle (1+x+x^2+\ldots)(1+x^5+x^{10}+\ldots)(1+x^{10}+x^{20}+\ldots)(1+x^{25}+x^{50}+\ldots)(1+x^{50}+x^{100}+\ldots).

So to get this coefficient, we just simplify the above to

\displaystyle \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})},

take the {n}-th derivative, evaluate at {x=0}, and divide by {n!}, right?

Well it's not actually obvious how to take these higher-order derivatives, but Newberg has a more subtle strategy.

The trick is to break the problem into two pieces:

  1. How many ways are there to make {k} dollars using only whole dollar amounts of each coin?
  2. How many ways are there to make {k} dollars using strictly less than one dollar's worth of each coin?

Since the individual denominations each divide 100, answers to the above two questions can be combined (convolved) to get the total number of ways to make {n} whole dollars. Explicitly, if {w(k)} is the answer to (1) and {f(k)} is the answer to (2), then the number of ways to make {n} whole dollars is

\displaystyle \sum_{k=0}^\infty f(k)w(n-k).

Note, of course, that {f(k)=0} for {k\geq5}, which simplifies this combination step considerably. (Equivalent to the above convolution: the product of generating functions for subproblems (1) and (2) is a generating function for the whole problem.)

Subproblem (1) is easy to solve with a generating function. The particulars of the denominations are irrelevant, except that they divide one dollar evenly, so we're asking for the number of ways to partition the set {\{1,\ldots,k\}} into 5 contiguous (possibly empty) subsets. This is the {k}-th coefficient of

\displaystyle (1+x+x^2+\ldots)^5\ =\ (1-x)^{-5}.

We can easily find all derivatives of this function. Using

\displaystyle \frac{d}{dx}(1-x)^{-a}\ =\ a(1-x)^{-a-1},

we get

\displaystyle \left.\frac{d^k}{dx^k}(1-x)^{-5}\right|_{x=0}\ =\ 5\cdot6\cdot7\cdots(k+4).

Dividing by {k!}, we get the answer to (1) as

\displaystyle w(k)\ =\ \frac{(k+1)(k+2)(k+3)(k+4)}{24}\ =\ {k+4\choose 4}.

In general, the number of ways to partition {\{1,\ldots,k\}} into {p>0} continguous subsets is {{k+p-1 \choose p-1}}, and this identity can be proved the same way. (Exercise: give a purely combinatorial proof.)

Subproblem (2) can also be solved with a generating function... and a computer algebra system. (Alternately/equivalently, it's a small enough problem to brute force with a short script.) The argument goes that {f(k)} is the {100k}-th coefficient of

\displaystyle (1+x+\ldots+x^{99})(1+x^5+\ldots+x^{95})(1+x^{10}+\ldots+x^{90})(1+x^{25}+x^{50}+x^{75})(1+x^{50}).

Since

\displaystyle 1+x+\ldots+x^{99}\ =\ (1+x+x^2+\ldots)(1-x^{100})\ =\ (1-x^{100})/(1-x)

and similarly for the other factors, the product above equals

\displaystyle \frac{(1-x^{100})^5}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})}.

The main benefit of this rewrite is that the quotient is easier to type into the CAS! Wolfram Alpha unfortunately times out on me, but Mathics can fully expand the 409-degree polynomial, from which we read off {f(0)=1}, {f(1)=287}, {f(2)=985}, {f(3)=325}, {f(4)=2}. (These are the same numbers Newberg got with the 100-cent coin included, which should come as no surprise, because that coin clearly can't contribute here.)

Finally then, the number of ways to change {n} dollars with our five coins is the convolution of {f} and {w},

\displaystyle \sum_{k=0}^4f(k)w(n-k)\ =\ w(n) + 287w(n-1) + 985w(n-2) + 325w(n-3)+2w(n-4).

Again relying on Mathics to perform the simplification (Wolfram Alpha apparently doesn't support intermediate function definitions), our final answer is

\displaystyle 1+\frac{55n+238n^2+380n^3+200n^4}{3},

exactly as predicted in section 2.

3. And beyond!

Newberg's approach can be adapted to the general coin changing problem as well. In the general case, any common multiple of the available denominations can take the role of the dollar in the preceding calculation, allowing the derivation of closed form solutions when the number of cents to be changed is divisible by the LCM of the denominations. Further modification of subproblem (2) allows for the derivation of closed form solutions for numbers of cents of a given residue mod the LCM. Thus we can in principle solve the general coin changing problem with an algorithm whose running time does not depend on the total amount of money to change.

The trade-off is that "compiling" such a closed form solution becomes quite costly as the number of denominations d and their LCM L grows: subproblem (2) involves the generation and collection of O(L**d) monomials!

The situtation can be improved somewhat via memoization/dynamic programming. Generation of monomials is incidental to subproblem (2); we really just want to calculate the number of ways to make certain amounts of money using less than L worth of each denomination. This suggests the following function definition.

@memo
def make_change_bdd(amt, denoms, bound, used):
    if amt < 0 or used >= bound: return 0
    if amt == 0: return 1
    if not denoms: return 0
    return ( make_change_bdd(amt, denoms[1:], bound, 0) +
        make_change_bdd(amt-denoms[0], denoms, bound, used+denoms[0]) )

The parameter used keeps track of the value used by the first coin in denoms, and is necessary to preserve "optimal substructure". Post memoization, make_change_bdd(A, denoms, b, 0) can be easily reconstructed from its O(A*d*b) subproblems. We need to evaluate the function for A up to O(L*d) (the degree of the polynomial in subproblem (2)) and with b = L. Thus we can at least solve (2) in O((L*d)**2) time.

Putting the pieces together, we might get something like the following. Experimentation confirms that the "compilation" step is still quite costly (e.g. 40 seconds for denoms = (17,19,23) at 2.2 GHz), but the "executable" function changer produced (and saved via memoization) is as fast as you could ever want.

Note that I've cheated slightly by not bothering to make the changer functions (that I'm calling closed form solutions) transparent to the user. One possible solution is to define a (rational coefficient) Polynomial class with its own __call__ and __str__ methods.

Notes

  1. Python forbids hashing mutable types like list, so it's important when using the memoized version to pass denoms as a tuple.
  2. On the topic of using lazily evaluated data structures as memoized functions, a truly gorgeous 3-line Haskell implementation of this one-coin-at-a-time approach is available on Rosetta Code (though it probably still uses O(A*d) space). It's basically a more complex version of my favorite ever Haskell one-liner
    fibs = 0:1: zipWith (+) fibs (tail fibs)

    which picks out the Fibonacci sequence as an infinite list defined in terms of two shifted copies of itself; fibs can be indexed into (forcing evaluation of an initial segment) in linear time.

  3. Annoyingly, xrange in 32-bit Python 2.7.3 won't accept arguments larger than 2**31-1, so I actually had to rewrite the for loop as a while/counter loop to get the result for $100M (10 billion cents).
Advertisements

4 thoughts on “Making change

  1. Hi, excuse me could you explain me how this works:
    window = [[0 for _ in range(d+1)] for _ in range(wsize)]
    i don’t understand this window is that like a matriz? Thank you so much

  2. I just came across this problem today. The way we solved it was to use Lagrange interpolation to evaluate the solution polynomial, using the DP values we already pre-computed up d times the LCM of the denominations. This way evaluation is only quadratic in d, the number of different denominations used.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s