Doc/Articles/Play201
At Play With J ... Table of Contents ... Previous Chapter ... Next Chapter
34. Greed
. By Eugene McDonnell. First published in Vector, 20, 1, (July 2003), 117-121.
My first experience of the British monetary system was in early 1953, in London. As was the case with many other visiting Americans, I felt daunted by the pound-shilling-pence currency. I had no idea what value the coins had. At a kiosk I picked up a newspaper, and then, expecting that a newspaper would be sold for just a few pennies, tendered, from the handful of coins I had, a smallish one. The vendor rapidly poured into my hand so many coins in change that I was completely unnerved. I took on faith that this was not a mistake, but I realized that I had better study the coins much more than I yet had. To this day I don’t know what the coin was that produced such a flood of change. To solve the problem, I got in the habit, when I bought something, of just holding out a handful of coins, expecting that sturdy British honesty would ensure that vendors would take only the coins that would satisfy the transaction. This seemed to work quite well.
This paper discusses the problem of making change. When change is made in a store, we are used to seeing the clerk reach into the till and then take coins from its separate compartments. Unless there is a shortage of one or more coins, this is done by taking as many of the largest coin as are needed, followed by as many of the next largest, and so on, down to the penny. This almost instinctive method is called the greedy algorithm by computer scientists. The design of many, if not all, currency systems is such that the greedy algorithm also minimizes the number of coins that make up the amount of change.
I’ll represent a set of coins by a list of the values in descending order. For example, the set of coins in the US^*^ is 25 10 5 1 ; the coins are called, in order, quarter, dime, nickel and cent, or penny. The list for European coinage is 200 100 50 20 10 5 2 1 . In order to be able to give just 1 pence in change it is necessary that every coinage set have as its least coin one that is worth just one penny. The change itself can be represented by a corresponding list with the values showing the number of coins of each denomination used. For example, 99 pence change in the US would be represented by 3 2 0 4 ; in Europe by 0 0 1 2 0 1 2 0 .
Although the greedy algorithm will give the fewest coins possible for any amount of change, it is not necessarily the case that existing coinage systems give the fewest number of coins possible. Jeffrey Shallit [1] recently suggested (with tongue firmly planted in cheek) that in order to make it possible in the United States to make change using the fewest coins, and still using just four values, the coinage should be replaced by one having coins worth either 25 18 5 1 or 29 18 5 1 cents. He showed that with the existing coins, assuming all values from 0 to 99 to occur equally often, which he admits may be far from the truth, the average number of coins needed to give change is 4.7; with either of his suggested sets only 3.89 coins would be needed. He recommended the 25 18 5 1 set, since only the 10-cent piece would need to be changed. To show the benefit of the proposal, note that to give 36¢ change, the minimum number of coins with the current system is three: 1 1 0 1 ; with the alternative, only two are needed: 0 2 0 0 .
Shallit points out that there is a problem with his suggested change, and it has to do with the failure of the greedy algorithm. For example, to give 36¢ change using the set 25 18 5 1 , the greedy algorithm gives the four-coin solution 1 0 2 1 , but the optimal solution, as shown above, needs only two coins: 0 2 0 0 . If a coinage system was such that the greedy algorithm was not always optimal, it would require such expertise in all those who make change to do so optimally that, if for no other reason, it would simply be too impractical. In the rest of this paper I’ll concentrate on a set of J functions for the greedy algorithm.
A Greedy J Algorithm
In looking for a solution to a programming problem, I frequently try to picture the steps required. For the greedy algorithm, the picture that eventually stabilized was of two linked lists: one, a list A, beginning with a list of the number of coins needed for each coin considered so far, initially empty, followed by the total amount of change needed; the second list, C, was of the coins not yet considered, initially the complete coinage set in descending order. The two lists were linked to form the list AC. Assuming these two lists were available, the processing required to obtain the next result was to replace the last item of A by the quotient and remainder of this last item divided by the leading coin of C, and C was then modified by removing its leading item. For example, assuming that a function CS was available, that performed one step of the change process, the steps in obtaining 99 pence change in the Euro system would be:
EU=: 200 100 50 20 10 5 2 1 A=: (i. 0) , 99 C=: EU ] AC=: A ; C +--+----------------------+ |99|200 100 50 20 10 5 2 1| +--+----------------------+ ] AC=: CS AC +----+------------------+ |0 99|100 50 20 10 5 2 1| +----+------------------+ ] AC=: CS AC +------+--------------+ |0 0 99|50 20 10 5 2 1| +------+--------------+ ] AC=: CS AC +--------+-----------+ |0 0 1 49|20 10 5 2 1| +--------+-----------+ ] AC=: CS AC +---------+--------+ |0 0 1 2 9|10 5 2 1| +---------+--------+ ] AC=: CS AC +-----------+-----+ |0 0 1 2 0 9|5 2 1| +-----------+-----+ ] AC=: CS AC +-------------+---+ |0 0 1 2 0 1 4|2 1| +-------------+---+ ] AC=: CS AC +---------------+-+ |0 0 1 2 0 1 2 0|1| +---------------+-+ ] AC=: CS AC +-----------------++ |0 0 1 2 0 1 2 0 0|| +-----------------++
The process stops when there are no more coins to be used. Since the last divisor is 1, only the quotient is germane, and after razing AC, the spurious remainder is discarded, forming the result R. A vector product shows that the number of coins provided does indeed give the needed amount of change:
] R=: }: ; AC 0 0 1 2 0 1 2 0 EU +/ . * R 99
We’ll start by building the nuts and bolts that go into making CS. This involves developing a new A and a new C, and linking them.
CS=: NA ; NC
The new A is formed by curtailing A and appending the result of the quotient-remainder function QR .
NA=: CA , QR
CA is straightforward:
CA=: }: @ > @ {.
QR uses the quotient-remainder primitive of J: the quotient and remainder of X divided by Y is given by (0,Y)#:X . For example, the quotient and remainder of 99 divided by 50 is 1 49. The two-part divisor is formed by appending the head of C, which is the largest remaining coin, to 0. The head of C is trivial:
HC=: {. @ > @ }.
The divisor is:
DR=: 0 , HC
The dividend is the current tail of A :
TA=: {: @ > @ {.
And QR is now easily formed:
QR=: DR #: TA
The new A is the curtailed current A appended with QR .
NA=: CA , QR
The new C is just the behead of the old C :
NC =: }. @ > @ {:
CS can now be used to obtain the successive results, as shown above. We need to find the number of times CS should be used, which is the number of coins in the coinage system, given by NS :
NS=: # @ > @ }.
A function which executes the change step function CS the correct number of times is ES :
ES=: CS ^: NS
After CS has been executed the proper number of times, the result is still two linked lists, the first list having a spurious item at the end, and the second list empty. To get the final result, the result of ES is razed and curtailed. The outermost function which encapsulates all that has preceded is MC :
MC=: }: @ ; @ ES
You’ll notice, I’m sure, that this is a great many defined functions. Perhaps it says something about my attention span. I prefer to think that by making every function as simple as possible, with as few steps as are meaningful, it is easier for me to test for errors as I go along. Since J has the fix adverb (f.), it is easy to obtain a single longish function, which on my computer executes eleven times faster, although when displayed it probably appears quite daunting. It’s not necessary to look at the result of fix, any more than one would look at the result of compiling a program written in a compiler environment. For the diehard masochist, I offer:
MCf=: MC f.
] q=: 5 !: 5 < 'MCf' NB. in character form
}:@;@(((}:@>@{. , (0 , {.@>@}.) #: {:@>@{.) ; }.@>@{:)^:(#@>@}.))
Notice that of the 45 tokens, ten are parentheses. The line above may make more sense if I use words for most of the tokens:
curtail@raze@(((curtail@A , (0 , head@C) #: tail@A) ; behead@C) ^: (tally@C))
For convenience, here are the functions that have been defined, in top-down order:
MC=: }: @ ; @ ES NB. make change: curtail raze IS
ES=: CS ^: NS NB. iterate change step NI times
NS=: # @ > @ }. NB. how many iterations: count C
CS=: NA ; NC NB. change step: new A link new C
NC=: }. @ > @ {: NB. behead C
NA=: CA , QR NB. new head: curtail A, append QR
CA=: }: @ > @ {. NB. curtail A
QR=: DR #: TA NB. divisor antibase tail A
TA=: {: @ > @ {. NB. tail A
DR=: 0 , HC NB. divisor: 0, head C
HC=: {. @ > @ }. NB. head C
Notes
^*^There is a 50-cent piece in the US, but it is rarely used; the half-dollar is as rare in circulation as the two-dollar bill—which is very rare.
Reference
[1] Shallit, Jeffrey, What this country needs is an 18¢ piece. Math. Intelligencer 25, 2, (2003), 20-23. Also available at Shallit’s website: http://www.cs.uwaterloo.ca/~shallit/papers.html. This gives pointers to the paper in two forms: PostScript and PDF.