I was flicking through Wikström’s «Functional Programming Using Standard ML», when I noticed he describes the problem of making up change for an amount of money `m` using coins of certain denominations (18.1.2, page 233). He says we “want a function `change` that given an amount finds the smallest number of coins that adds to that amount”, and “Obviously, you first select the biggest possible coin”. Here’s his solution in ML:

exception change; fun change 0 cs = nul | change m nil = raise change | change m (ccs as c::cs) = if m >= c then c::change (m-c) ccs else change m cs;

It’s pretty neat. The recursion proceeds by either reducing the magnitude of the first argument (the amount we are giving change for), or reducing the size of the list that is the second argument (the denominations of the coins we can use); so we can tell that the recursion must terminate. Yay.

It’s not right though. Well, it gives correct change, but it doesn’t necessarily find the solution with fewest number of coins. Actually, it depends on the denominations of coins in our currency; probably for real currencies the “biggest coin first” algorithm does in fact give the fewest number of coins, but consider the currency used on the island of `san side-effect`, the `lambda`. `lambdas` come in coins of Λ1, Λ10, and Λ25 (that’s not a wedge, it’s a capital lambda. It’s definitely not a fake A).

How do we give change of Λ30? { Λ10, Λ10, Λ10 } (3 tens); what does Wikström’s algorithm give? 1 twenty-five and 5 ones. Oops.

I didn’t work out a witty solution to the fewest number of coins change, but I did create, in shell, a function that lists all the possible ways of making change. Apart from trivial syntactic changes, it’s not so different from the ML:

_change () { # $1 is the amount to be changed; # $2 is the largest coin; # $3 is a comma separated list of the remaining coins if [ "$1" -eq 0 ] ; then echo ; return fi if [ -z "$2" ] ; then return fi _change $1 ${3%%,*} ${3#*,} if [ "$1" -lt "$2" ] ; then return fi _change $(($1-$2)) $2 $3 | while read a ; do echo $2 $a done } change () { _change $1 ${2%%,*} ${2#*,}, }

Each solution is output as a single line with the coins used in a space separated list. `change` is a wrapper around `_change` which does the actual work. The two base cases are basically identical: «”$1″ -eq 0» is when we have zero change to give, and we output an empty line (just a bare `echo`) which is our representation for the empty list; «-z “$2″» is when the second argument (the first element of the list of coins) is empty, and, instead of raising an exception, we simply return without output any list at all.

The algorithm to generate all possible combinations of change is only very slightly different from Wikström’s: if we can use the largest coin, then we generate change both without using the largest coin (first recursive call to `_change`, on line 12) and using the largest coin (second recursive call to `_change`, on line 16). See how we use a `while` loop to prepend (cons, if you will) the largest coin value to each list returned by the second recursive call. Of course, when the largest coin is too large then we proceed without it, and we only have the first recursive call.

The list of coins is managed as two function arguments. $2 is the largest coin, $3 is a comma separated list of the remaining coins (including a trailing comma, added by the wrapping `change` function). See how, in the first recursive call to `_change` $3 is decomposed into a head and tail with ${3%%,*} and ${3#*,}. As hinted at in the previous article, «%%» is a greedy match and removes the largest suffix that matches the pattern «,*» which is everything from the first comma to the end of the string, and so it leaves the first number in the comma separated list. «#» is a non-greedy match and removes the smallest prefix that matches the pattern «*,», so it removes the first number and its comma from the list. Note how I am assuming that all the arguments do not contain spaces, so I am being very cavalier with double quotes around my $1 and $2 and so on.

It even works:

$ change 30 25,10,1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 10 1 1 1 1 1 1 1 1 1 1 10 10 10 25 1 1 1 1 1

2012-03-13 at 09:17:28

That’s hilarious! Have you been doing a lot of shell programming recently?

The only caveat I’d add is that without memoization this algorithm has exponential running time (as I learned when solving Project Euler problem 31).

2012-03-13 at 17:09:50

I’ve been doing a bit more shell programming, but i’m trying to amplify that by doing a lot more shell programming than i need to. And make 2012 the year of shell.

2012-03-13 at 10:23:35

Of course, the

realproblem is normally “using coins of denominations D0,D1,… transact amount X from A to B by A passing some coins to B then B returning change to A, so as to minimise the total number of coins exchanged. The way to make 9p using UK currency, for example, is give them a 10p piece and get a 1p piece in change, for a total of only two coins.Every now and then I re-visit the topic of optimising the denominations to minimise the number of coins exchanged (as opposed, of course, to maximising convenience for those used to a denary system) in an average transaction. Then I remember there’s no good definition of “an average transaction” and give up again.

2012-05-04 at 09:54:13

Why would you minimise the total number of voins exchanged? I often try and maximise (number I give – number I receive), in order to “get rid of change”.

2012-03-13 at 13:51:22

I seem to recall reading that there was some serious mathematics done on the subject of optimizing denominations while minimizing number of coin denominations, and the result came out basically the same as the US coin denominations. (0.01, 0.05, 0.10, 0.25).

2012-03-13 at 17:13:38

we have 1p, 2p, 5p, 10p, 20p, 50p. It does seem that intuitively it would be better to have a 25p coin instead of a 20p coin, because the 20p coin can only save 1 coin in change.

Holland used to have a 2½ guilder coin. Very sensible.

2012-03-21 at 09:30:17

That’s a coincidence: I just came back from Cuba where they have the following system for their convertible currency:

Coins: 0.01 0.02 0.05 0.10 0.25 0.50 1.00

Notes: 1.00 _3.00_ 5.00 10.00 20.00 50.00 …

The three peso note got some getting used to! But it made me think, even then: Is this problem related to the “optimal radix” problem where (IIRC) the “best” radix is “e” (for some definition of “best”).

So maybe the three peso note isn’t such a bad choice after all. Does that mean they should shift their five peso note to seven pesos?