So here's a venerable little problem, simple to state, tough to get
right, even tougher to program. I give you an amount, a, and a list of
currency denominations, l; you give me back
1. the different configurations or partitions, that is, the
multipliers or coin counts of each of the denominations that add up
to the given amount
2. the most efficient partition, meaning that with the least number of
coins
3. an indication whether the most efficient partition is unique
For instance, I give you a = 40 cents, and l = [25,10,5,1], that is,
quarters, dimes, nickels, and pennies; you give me back the following
31 partitions:
{[1,1,1,0], [1,1,0,5], [1,0,3,0], [1,0,2,5], [1,0,1,10], [1,0,0,15],
[0,4,0,0], [0,3,2,0], [0,3,1,5], [0,3,0,10], [0,2,4,0], [0,2,3,5],
[0,2,2,10], [0,2,1,15], [0,2,0,20], [0,1,6,0], [0,1,5,5], [0,1,4,10],
[0,1,3,15], [0,1,2,20], [0,1,1,25], [0,1,0,30], [0,0,8,0], [0,0,7,5],
[0,0,6,10], [0,0,5,15], [0,0,4,20], [0,0,3,25], [0,0,2,30], [0,0,1,35],
[0,0,0,40]}
with the first one, consisting of 3 coins, being the most efficient and
obviously unique, by inspection.
If we're allowed quarters only, that is, the denominations are the
list [25], we can't do it, so the partitions are the empty set. If the
denominations are [25,10], that is, quarters and dimes, the only
partition is [0,4]. If the denominations are [25,10,5], adding nickels
to the mix, we get the following partitions: {[1,1,1], [1,0,3],
[0,4,0], [0,3,2], [0,2,4], [0,1,6], [0,0,8]}, for seven distinct
possibilities.
Ok, so what's a general rule or procedure for computing these
configurations or partitions?
To come up with the most efficient partition, so long as there are
pennies in the mix, I came up with the following pretty little Haskell
program (http://www.haskell.org):
makeChange amt [] = []
makeChange amt (den : dens) =
(amt `div` den) : makeChange (amt `mod` den) dens
This just says that when the denominations are nil, the result is nil,
otherwise, the first element of the partition is the integer quotient
of the amount with the largest denomination, and the rest of the
partition is, recursively, the same procedure applied to the remainder
of the integer division and the rest of the denominations. Neat and
clean. Trouble is, it's not robust. It MUST have pennies in the mix to
pick up all the 'slop' -- the remainders not divisible by the next
highest denomination from pennies. If not, it will fail when a = 40
and l = [25,10], for instance.
Well, I thought, the general solution will fall quickly to my years of
accumulated experience and treachery, to my rapier-like cleverness and
finesse, to a relentless assault of blunt-force trauma, blah, blah,
blah.
Being a physicist, the first thing to occur to me was DOT PRODUCT!
Since the inner product of the denominations and each configuration
must equal the given amount, each solution started to look like a
vector in a lattice space, where the basis vectors were "lengths"
equal to each denomination. The difficulty with this approach is that
the needed length of the vector is a "Manhattan" metric rather than a
Euclidean. So much for that idea (though, there might still be
something there).
After spending some time with the rapier, the bludgeon, and outright
treason, I concluded that backtracking in an n-ary tree-shaped data
structure was necessary, since every attempt to generate the "next"
from a "prior" resulted in duplicates. I could stuff the duplicates in
a hash table and simply refused to generate them a second time, but
that was too ugly, even for me.
I decided to sneak a peek at history, and found that this problem has
an extensive literature. Even determining the existence of a solution
is NP-hard. However, there do exist recursive procedures, for
instance, those found at http://theory.cs.uvic.ca/~cos/. They are
based on some theorems that can be found in Herbert Wilf's lecture on
integer partitions:
http://www.math.upenn.edu/%7Ewilf/PIMS/PIMSLectures.pdf
As a bonus enticement, let me say that this subject was attacked by
the famous Ramanujan, who closed it out with one of those stupendously
rococo formulas of his involving 24-th roots of unity in the complex
plane, pi times square roots of two, and derivatives of hyperbolic sin
functions! It was one of his crowning achievements, and must be seen
to be believed. He was surely a breed apart, especially when attacking
integer partitions.