The Problem:
Not long I was asked for advice, because a problem-type in elementary math (indeed from a first-grader) proved to be quite a challenge for my nephew and I was if I had some quick tips.
The problem is easily stated:
The pupils at this stage know about the basic coins and bills: 1€, 2€, 5€ and 10€ – now there is a given price for some nice item (for example a book for 10€) and there are a couple of purses each with a number of money-items (coins or bills) in them but not which.
For the book example there might be a purse with 5 items. The kids are asked to write down what coins or bills are in there – a sample solution here would be of course five 2€-coins.
The hard part is of course teaching this to a kid without our day-to-day experience with this kind of problem (it the end he found the spark and now it’s of course “easy”).
But the problem is just the right think for a short post on combinatorial algorithms without the 100’s copy of “how to get all permutations” (of course it’s not that different).
What the algorithm should find
I don’t want to solve the problem as it is but I want the algorithm to just find each combination of coins/bills for a given price (and available coins/bills).
So given a list of those:
avaiableUnits=[1.0; 2.0; 5.0; 10.0]
it should for example find all combinations for 12€ – here are the tests:
namespace LearnMoneyCombinatorics.Core.UnitTests open System open NUnit.Framework open FsUnit open LearnMoneyCombinatorics.Core [<TestFixture>] type ``Using Combinations for 12 EUR with only 1eur, 2eur, 5eur and 10eur - coins and notes``() = let generator = new Combinations(avaiableUnits=[1.0; 2.0; 5.0; 10.0]) let amount = 12.0 let validCombinations = generator.GetValidCombinations amount [<Test>] member test. ``there are 15 combinations``() = validCombinations |> Seq.toArray |> should haveLength 15 [<Test>] member test. ``1 x 10€ and 1 x 2€ is a valid combination``() = validCombinations |> should contain (collect [10.0 |> times 1; 2.0 |> times 1] ) [<Test>] member test. ``1 x 10€ and 2 x 1€ is a valid combination``() = validCombinations |> should contain (collect [10.0 |> times 1; 1.0 |> times 2] ) [<Test>] member test. ``2 x 5€ and 1 x 2€ is a valid combination``() = validCombinations |> should contain (collect [5.0 |> times 2; 2.0 |> times 1] ) [<Test>] member test. ``2 x 5€ and 2 x 1€ is a valid combination``() = validCombinations |> should contain (collect [5.0 |> times 2; 1.0 |> times 2] ) [<Test>] member test. ``1 x 5€ and 3 x 2€ and 1 x 1€ is a valid combination``() = validCombinations |> should contain (collect [5.0 |> times 1; 2.0 |> times 3; 1.0 |> times 1] ) [<Test>] member test. ``1 x 5€ and 2 x 2€ and 3 x 1€ is a valid combination``() = validCombinations |> should contain (collect [5.0 |> times 1; 2.0 |> times 2; 1.0 |> times 3] ) [<Test>] member test. ``1 x 5€ and 1 x 2€ and 5 x 1€ is a valid combination``() = validCombinations |> should contain (collect [5.0 |> times 1; 2.0 |> times 1; 1.0 |> times 5] ) [<Test>] member test. ``1 x 5€ and 7 x 1€ is a valid combination``() = validCombinations |> should contain (collect [5.0 |> times 1; 1.0 |> times 7] ) [<Test>] member test. ``6 x 2€ is a valid combination``() = validCombinations |> should contain (2.0 |> times 6) [<Test>] member test. ``5 x 2€ and 2 x 1€ is a valid combination``() = validCombinations |> should contain (collect [2.0 |> times 5; 1.0 |> times 2]) [<Test>] member test. ``4 x 2€ and 4 x 1€ is a valid combination``() = validCombinations |> should contain (collect [2.0 |> times 4; 1.0 |> times 4]) [<Test>] member test. ``3 x 2€ and 6 x 1€ is a valid combination``() = validCombinations |> should contain (collect [2.0 |> times 3; 1.0 |> times 6]) [<Test>] member test. ``2 x 2€ and 8 x 1€ is a valid combination``() = validCombinations |> should contain (collect [2.0 |> times 2; 1.0 |> times 8]) [<Test>] member test. ``1 x 2€ and 10 x 1€ is a valid combination``() = validCombinations |> should contain (collect [2.0 |> times 1; 1.0 |> times 10]) [<Test>] member test. ``12 x 1€ is a valid combination``() = validCombinations |> should contain (1.0 |> times 12)
How to solve
The tests give a pretty good indication of how to solve this – start with the biggest bill/coin still fitting the needed price, subtract all possible multiples of this from the price and recursively find the combinations for the rest-price and combine those together.
This is really a standard algorithm to solve this kinds of problems – divide and conquer with recursion.
Let’s do a few steps to get a feeling for this.
We have to spend 12€ so we can use one or zero 10€-bills.
Let’s use one bill – then we still have to spend 2€.
For 2€ we can take no 10€ bill, no 5€ bill but one or zero 2€ coins so let’s take one – we have nothing more to pay so we have found a combination: [1×10€; 1×2€].
For the next trace back and take no 2€ – then we can take next two, one or none 1€ coins – take two and again we found a combination: [1×10€; 2×1€], …
The implementation
To hold the data I use two simple structures – one to remember the coin/bill together with its multiplicity (how many of those you use for a combination) and the combination itself being only a set of those structures from before – the code will be much more clearer than this “description” so don’t worry
Warning: I did not bother to make this tail-recursive (to make it a bit more readable) but I choose to use sequences to get a one-at-a time combination instead of waiting to get all at once – you can easily switch by changing the Seq.xyz methods to List.xyz ones and changing the seq {…} block to a List.combine.
Here is the code:
namespace LearnMoneyCombinatorics.Core open System type CombinationItem = int * float type Combination = CombinationItem Set [<AutoOpen>] module CombinationHelpers = let collect items : Combination = items |> Set.unionMany let times count amount : Combination = (count, amount) |> Set.singleton let total (comb : Combination) : float = comb |> Set.fold (fun t (c, u) -> t+(float c * u)) 0.0 type Combinations(avaiableUnits : float seq) = let maxCount u (a : float) = Math.Floor(a / u) |> int let avUnitsDesc = avaiableUnits |> Seq.sortBy (fun a -> -1.0 * a) |> Seq.toArray let rec createCombinations restA i : Combination seq = if i >= avUnitsDesc.Length && restA > 0.0 then Seq.empty elif restA = 0.0 then Set.empty |> Seq.singleton else let curUnit = avUnitsDesc.[i] let maxC = restA |> maxCount curUnit let combine count = let cur = if count = 0 then Set.empty else curUnit |> times count let remaining = createCombinations (restA - float count * curUnit) (i+1) remaining |> Seq.map (fun r -> Set.union cur r) seq { for i in [maxC .. -1 .. 0] do yield! combine i } let combinations amount = createCombinations amount 0 member c.GetValidCombinations(amount) : Combination seq = combinations amount
All the work is done inside createCombinations – a recursive function.
The parameters a first the rest-price to find and second a index into the ordered available coin/bill values (what next to try – so to say).
It first checks: if there is still money to spend (restA > 0.0) and we have no more coins to try we fail (Seq.empty back).
If-not (that is if we have paid for all) and we don’t have any more and return a empty combination.
In every other case we look check how many times we can use the current value (curUnit) to spend on the rest-amount of money (maxCount) combine every one of these recursively with all the possible combinations for the rest-amount to finally yield those in a sequence.
What’s important to understand is that – as in the permutation case – we have to remember that we tried – let’s say 10€ – and do not try those again – this is done here by using the ordered amount-list and the index into this.
That’s it for today – I hope you enjoyed this brief episode.