Problem 74

http://projecteuler.net/index.php?section=problems&id=74
いわゆる、すなおなアルゴリズム。
よって、遅い。

import Data.List
import Data.Char
next = toInteger.sum.map (f.digitToInt).(show::Integer->String)
    where f n = product [1..n]
link = length.link' [] . iterate next
    where link' xs (y:ys) 
              | elem y xs = xs
              | otherwise = link' (xs++[y]) ys
main =print.length.filter (==60).map link $[1..10^6]

高速化への一歩は計算結果の再利用だろう。
つまりDPすれば速くなるのでは？
計算量はlinkを構成する際の数字が単調減少でないから、良く分からない。が
各数字のlink長は、次の数字（各桁の階乗和）のlink長+1だから
その数字が計算してあればそれ以降のlinkを構成する必要はない。
そして、各桁の階乗和はそんなに大きくならないはず（link最長は60ナンだし）。
だから多分、各桁の階乗和を計算する回数は10^6くらい。

ん？大して変わってなくね？
素直にやっても各桁の階乗和を計算するのは
高々60*10^6だ。

いや、しかし、好意的に解釈すれば60倍速くなるんだよ。
というか、高々60倍の高速化にしかならない。
（各桁の階乗和が計算時間の大部分を占めているという仮定のもとでは）
たぶん領域計算量は増えるんだろうな、表を作るから。

結論：DP使っても大して速くならないのでは？

実装。

import Data.List
import Data.Array.IArray
import Data.Char

linkArray m = lArray::Array Integer Int
    where lArray  = listArray(1,m)[link n|n<-[1..m]]
          link  871    = 2
          link  45361  = 2
          link  872    = 2
          link  45362  = 2
          link  169    = 3
          link  363601 = 3
          link  1454   = 3
          link n | n== next n = 1
                 |  otherwise = link'.minPerm$n
          link'  n | next n <= m   = (1+).(lArray!).next$n
                   | otherwise     = (1+).(link.next)$n

minPerm ::Integer -> Integer
minPerm n = let (zs,xs)=span(=='0').sort.show$n
           in read$head xs : zs++tail xs
next ::Integer -> Integer
next = toInteger.sum.map (f.digitToInt).show
    where f n = product [1..n]
main = print.length.filter(==60).elems.linkArray$1000000

やっぱりあまり速くなかった。
置換の計算をさぼっているので少しは速いはず。たぶん。

というか実際必要なのは数字の組だから、1から順に探すのではなく、
数字の組を探せばよい。
こっちはDPより速くなるだろう。多分オーダーが1つ落ちる。
だから100倍ぐらい速くなるはず。でも、もうこの問題は飽きた。