# 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.