I remember reading SICP. It's a lot of fun. The recursive algorithm reminds me of something I was just looking at the other day, the Chu-Vandermonde identity. One obvious way to speed it up is memoization. But I wonder if that would be as effective in this case as for Fibonacci. Another way would be to just handle the penny case by just outputting 1 straight away if amount >= 0, and handle the penny-and-nickel case by outputting 1+floor(amount/5). I'd imagine that just doing this would speed up the program quite a bit. But a straight-up, non-recursive calculation in one fell swoop? I'm not sure how to do that.
Sure, why not? It's still tree recursion after all. You just have to use an extra procedure that takes the change amount and how many coin values you have. e.g. For the UK coin values are 1, 2, 5, 10, 20, 50, 100 and 200 so there are 8 coin values. So instead of you'd use cc(amount, num_coins) and you memoize cc with indexes of amount and num_coins But I wonder if that would be as effective in this case as for Fibonacci.
count_change(amount) count_change(amount)
You're right. I hadn't quite thought it through, but it would work well: eg. for 8 coin values, if you need to calculate the number of ways to make 2.00, you need to make at most 200*8=1600 calls to the recursive function. So you get O(n) efficiency. But it still seems like you should be able to do better: O(1) would be possible with a closed-form formula. edit: Oh, I noticed you actually implemented it with memoization. Great!
That's way beyond my maths ability. Do you think you could find such a formula? I know there's Binet's formula for Fibonacci, but it's impractical for larger numbers as the floating point errors start to affec tthe results (on most machines anyway.) O(1) would be possible with a closed-form formula.
Yeah, it's tough, I don't really know how to go about it. But here's at least a demonstration for three denominations, {1, 2, 5}: (n is the total amount to add up to) numfives = math.floor(n/5.)+1 return int( numfives * (n % 5 + n + 3)/4 - (numfives % 2) * (n % 2 - 0.5) / 2. ) Disgusting, I know! But it works: I double checked it against your code, it gives the same result up to n=5000. An estimate for four denominations {1, 2, 5, 10} is n^3/600; for five denominations {1, 2, 5, 10, 25}, n^4/60000. I got these by summing crudely and dropping low order terms. They seem to be asymptotic: the estimate for five denominations is accurate to within 5% of the true value for n > 2000. That might seem silly but count_change does get quite slow for n >> 10^6 (that's $10,000.00), while the approximation is good to within 0.01%. edit: You could write a program that returns an estimator function for a given set of denominations. See Faulhaber's formula. def onetwofive(n):
I'm impressed you managed a solution for 3 coins. > count_change does get quite slow for n >> 10^6 (that's $10,000.00) From a pure math angle, both memo & dynamic programming versions are linear in time and space. As you said though, those numbers are growing exponentially meaning the space will grow exponentially too.