Project Euler 24

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

この問題は手計算レベルの計算量で済みます。

let rec factorial n = if n = 0 then 1 else n * (factorial (n - 1))
let to_number a = List.fold (fun x y -> x * 10L + int64 y) 0L a

let rec solve (a : int list) n r =
   if r = 0 then
      a
   else
      let f = factorial n
      let q = r / f
      let b = List.filter (fun n -> n <> a.[q]) a
      a.[q] :: (solve b (n - 1) (r % f))

let N = int 1e6
printfn "%d" (to_number (solve [0..9] 9 (N - 1)))

しかし、ここはあえて順列を出してみましょう。F#にはどうやら順列は用意されていないので自作します。Python風に書くと、

let rec permutations (a : int seq) = seq {
   if Seq.isEmpty a then
      yield a
   else
      for h in a do
         for e in permutations (Seq.filter (fun n -> n <> h) a) do
            yield (Seq.append (seq { h..h }) e)
}

もう少し短くHaskell風に書くと、

let rec permutations (a : int seq) =
   if Seq.isEmpty a then
      seq { for i in 0..0 -> a }
   else
      Seq.concat (Seq.map (fun h ->
         Seq.map (fun e -> (Seq.append (seq { h..h }) e))
            (permutations (Seq.filter (fun n -> n <> h) a))) a)

とても遅いのでSequenceをListにしたところメモリが足りなくなりました。

let to_number a = Seq.fold (fun x y -> x * 10L + int64 y) 0L a

let rec permutations (a : int seq) =
   if Seq.isEmpty a then
      seq { for i in 0..0 -> a }
   else
      Seq.concat (Seq.map (fun h ->
         Seq.map (fun e -> (Seq.append (seq { h..h }) e))
            (permutations (Seq.filter (fun n -> n <> h) a))) a)

let N = int 1e6
printfn "%d" (to_number (snd
               (Seq.head (Seq.filter (fun t -> fst(t) = N)
                  (Seq.zip (seq { 1..N }) (permutations { 0..9 }))))))