Well, I had to get one little theorem from the literature, but I nailed the coin-counting problem without backtracking. This is pretty nice. The theorem (in Wilf's cited lecture, and in the Combinatorica book, and implied in SICP (Structure and Interpretation of Computer Programs)) requires us to look at not just p(n), the number of partitions of n, but p(n,k), the number of partitions where the maximum species is k. The theorem is that p(n,k) = p(n-k,k) + p(n,k-1). That's a little difficult to parse mathematically and a little tricky to prove, but it translates, programming-wise, into a statement so clear and blatantly obvious it had me slapping my forehead. It's nice that insights from programming sometimes feedback into math, isn't it? Ok, here it is:
Let's call a coin (or species) of value k a k-coin. So a quarter is a 25-coin.
When the highest coin species is a k-coin, the partitions are of two kinds: those where there are k-coins and those where there are no k-coins (DUUUUH). But, this is key, and permits us to write a recursion and to PROVE the result: the partitions where there are k-coins are for amounts less than n. In fact, we can write the list of partitions where there ARE k-coins as ones with 1 k-coin appended to the list of partitions for amount n-k. Pretty cool, it works, and it allowed me to write and verify the following Haskell program in just a few minutes:
-- This is the type of the program named "pay"
pay {- amt species -} :: Amount -> Species -> Multipliers
-- These are the auxilliary types; [square brackets enclose Lisp-like lists]
type Amount = Integer
type Species = [Integer]
type Multipliers = [[Integer]]
-- This function lets us put zeros in front of all the lists in a list
prepends anInt [] = []
prepends anInt aList = map (\l -> (anInt : l)) aList
-- This function lets us increment the first element in a list ...
bumpFirst [] = []
bumpFirst (l:ls) = ((l+1):ls)
-- And this one lets us increment the first elements of all the lists in our list of partitions
bumpFirsts [] = []
bumpFirsts aList = map bumpFirst aList
-- Here we go. The list of partitions when the list of species is empty is a list of the empty partition.
pay amt [] = [[]]
-- If we have just ONE species at the end of a list of species, just divide the amount by the species
-- with error checking of course
pay amt (spc : [] )
| (amt `mod` spc) == 0 = [[ amt `div` spc ]]
| otherwise = error "can't make change; sorry"
-- Finally, here is the meat of the little theorem. (spc:spcs) is a list comprehension that matches
-- the highest species (our k-coin) to the variable spc, and the rest of them to spcs. Gotta love it.
pay amt (spc : spcs)
| (amt-spc) >= 0 = (bumpFirsts ((pay (amt-spc) (spc : spcs))))
++ (prepends 0 (pay amt spcs))
| otherwise = prepends 0 (pay amt spcs)