How many ways can you make change for a dollar? This post points to two approaches to the problem, one computational and one analytic.
SICP gives a Scheme program to solve the problem:
(define (count-change amount) (cc amount 5)) (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc amount (- kinds-of-coins 1)) (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins))))) (define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 1) ((= kinds-of-coins 2) 5) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50)))
Concrete Mathematics explains that the number of ways to make change for an amount of n cents is the coefficient of zn in the power series for the following:
Later on the book gives a more explicit but complicated formula for the coefficients.
Both show that there are 292 ways to make change for a dollar.
I put that formula into Mathematica and I replicated the result that the coefficient of z^100 is 292. I then thought I’d try it with British currency. Ours is similar to yours, but we have also have a 2p coin and we have a 20p coin instead of 25 cents. Pretty similar, I thought, but the result I get is that there are 4562 ways of changing a British pound! I’m a newbie at Mathematica, so I could well have made a mistake.
Have I done it wrong, or does a small change in the coinage make a huge change to the result?
Blaise: The US used to have a two cent coin. I had such a coin minted in 1864. I may still have it somewhere.
My guess is having a 2p coin creates a lot more possibilities. Maybe the most possibilities come from having lots of small denominations close together.
Can you show us the “more explicit but complicated formula for the coefficients” please?
Dumb R program:
Well that didn’t show up too well, but I think you get the drift. Unsurprisingly, it gives the same answer.
John S: I edited your previous comment, changing the code tags to pre tags.
The R code is dumb but easy to understand. It takes 1.16 s for the US example on my Core i7 and 72 79 s for the British example.
Bill Gasarch had a post about this a few weeks ago. He points out the two solutions you give, then derives a closed-form solution: http://blog.computationalcomplexity.org/2014/06/how-many-ways-can-you-make-change-of-n.html
I used scheme’s quasiquoting ability to expand out the recursive calls in the scheme code, this way you could visualize the shape of that computation.
For anyone that does either the brute force or the power series version to get the answer, realize that with their closed form the book also gives the ways to make change for $1,000,000. Plugging their numbers into scheme shows it can be calculated basically instantly. Using the brute force, I wouldn’t expect an answer anytime soon. (Granted… I haven’t tried in a while. Just saying.)
racket@> (+
(binomial 2000004 4)
(* 45
(binomial 2000003 4))
(* 52
(binomial 2000002 4))
(* 2
(binomial 2000001 4)))
66666793333412666685000001
I’m still trying to go through that book. The writing style really is very very fun. However, this sort of analysis is far removed from what I typically have to do, so it is hard for me to stay with it.