Wednesday, June 2, 2010

Problem 31: How many different ways can £2 be made using any number of coins?

More fun with recursive sequence expressions! In this solution, we generate all of the combinations instead of only counting them.

let problem31c =
    let combinations amt coins = //produce all ascending combinations starting with start
        let rec combinations combo =
            seq{ let sum = List.sum combo
                 if sum = amt then 
                     yield combo
                 elif sum < amt then 
                     yield! coins 
                            |> Seq.filter ((<=) combo.Head) //to generate combinations instead permutations
                            |> Seq.collect (fun c -> combinations (c::combo)) }
        seq {for start in coins do yield! combinations [start]}  //concat all ascending combinations for each start
    combinations 200 [1;2;5;10;20;50;100;200] |> Seq.length

No comments:

Post a Comment