an interesting combinatorial algorithm straight from elementary-school

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 Smiley

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.