We did almost this exact problem earlier this year on my course at uni but using the functional language ML, and actually returning a list of lists of ways to make the change. The solution is really neat in ML and since I have exams in a month or so I thought it wouldn't be such a bad idea for me to go over it and try to explain it to the other monks. I'll give the code first and then try and explain what it does.

1.    fun change (till, 0) = [[]]
2.      |  change ([], amt) = []
3.      |  change (coin::till, amt) = 
4.        if amt < coin then change(till, amt)
5.        else
6.        let fun allchange [] = []
7.            | allchange (cs::css) = (coin::cs) :: allchange css
8.        in allchange (change (coin::till, amt - coin)) @ change (til
+l, amt)
 9.       end;
[download]

The first line starts our function declaration and matches the input pattern of some list of coins that we can use (till) and an amount left over to make of 0. There is exactly one way to do this, an empty list of coins, so we return a list (the outer set of square brackets) containing the empty list (the inner set of square brackets). Line 2 is a second base case: we have run out of suitable types of coin, but we still need to make change. In this case there are no solutions so we return the empty list. From here onwards we get into the recursive magic, the case where we have a list of coins (the first of which is called coin, the rest of the list being contained in till) and an amount we are aiming to make. If the coin at the front of the list is too big, we simply discard it and try making change for that amount using the other coins in the till with a recursive call to change(till, amount) (line 4). Otherwise we define a new function allchange which takes a list of lists (cs is a list of coins, css is a list of such lists) and adds a coin to the front of all lists of coins in that list (line 7). We then call allchange on all the solutions found by the recursive call to change(till, amt-coin) and append (@) it to the list of ways of simply making change from coin (ie always taking the biggest coin we can).

Hopefully that makes sense, all the magic happens in line 8. It seemed like a pretty neat solution and short even in comparison with the Perl ones on offer (even if you do have to invest more brain power to understand it).

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.