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.