Project Euler 30

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

重複組合せを自作しました（1⁵ + 2⁵ + 2⁵ = 2⁵ + 1⁵ + 2⁵だから）。yieldを使うと簡単ですね。

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 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 m = if m = 0 then []
                     else (digits (n / 10) (m - 1)) @ [n % 10]
let to_number a = List.fold (fun x y -> x * 10 + y) 0 a

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

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

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