ScalaでProject Euler（42）

Problem 24

この問題には順列を生成する練習という面もあります。生成はIteratorで簡単に実現できます。

import scala.testing.Benchmark

// List(1, 2, 3) => (1, List(2, 3)), (2, List(1, 3)), (3, List(1, 2))
def pops[T](a :List[T]) :Iterator[(T,List[T])] = {
    def next(s :(List[T],T,List[T])) = s match {
        case (b, e, Nil) => (Nil, e, Nil)
        case (b, e, h1 :: t1) => (b ++ List(e), h1, t1)
    }
    
    Iterator.iterate((Nil :List[T], a.head, a.tail))(next).
                        take(a.size).map(s => (s._2, s._1 ++ s._3))
}

def permutations[T](a :List[T]) :Iterator[List[T]] =
    if(a == Nil)
        Iterator(Nil)
    else
        for((e, b) <- pops(a); c <- permutations(b))
            yield e :: c

def solve() = {
    val N = 1e6.toInt
    val a = List.range(0, 10)
    println (permutations(a).drop(N - 1).next.foldLeft(0L)(_ * 10 + _))
}

object Test extends Benchmark {
    def run() = solve
}

println (Test.runBenchmark(10))