Project Euler 34

http://projecteuler.net/index.php?section=problems&id=34

Problem 30とほとんど同じです。やはり重複組合せを使います。

let rec factorial n = if n = 0 then 1 else n * (factorial (n - 1))

let rec repeated_combination a n = seq {
   if n = 0 then
      yield []
   else if a <> [] then
      for b in repeated_combination a (n - 1) do
         yield (List.head a) :: b
      for b in repeated_combination (List.tail a) n do
         yield b
}

let rec digits n = if n = 0 then [] else (digits (n / 10)) @ [n % 10]
let rec pow n e = if e = 0 then 1 else n * (pow n (e - 1))

let rec max_num n = if (factorial 9) * n < (pow 10 n) - 1 then n
                        else max_num (n + 1)

let N = max_num 1
let s = seq {
    for n in 2..N do
        for a in repeated_combination [1..9] n ->
          (a, List.sum [ for d in a -> factorial d ])
}
let is_valid x = fst x = List.map (fun d -> if d = 0 then 1 else d)
                                                        (List.sort (digits (snd x)))
let v = Seq.sum (Seq.map (fun x -> snd x)
                        (Seq.filter is_valid s))
printfn "%d" v