HR F#: Pascal's Triangle

The second problem from the Recursive subdomain is printing Pascal's Triangle for given n.

Pascal's triangle is named after famous French mathematician from XVII century, Blaise Pascal. His findings on the properties of this numerical construction were published in this book, in 1665. Year before Great Fire of London.

The first row of the triangle is just one. (N+1)th row is constructed from Nth row by prepending and appending the sums of pairs from the Nth row with 1s:

row(0) =     1
row(1) =    1 1
row(2) =   1 2 1
row(3) =  1 3 3 1
row(4) = 1 4 6 4 1
row(n+1) = 1 (row(n)[0]+row(n)[1]) (row(n)[1]+row(n)[2]) ... 1

The k-th element of the n-th row can be calculated by n!/(k! (n-k)!) so the straightforward solution is just a single for with a factorial routine:

let rec f n =
    match n with | 0 | 1 -> 1 | _ -> n * f (n-1)
let line n =
  seq { for k in 0..n do yield ((f n) / ((f k) * f (n-k))) }

This solution works well for the test data but it is a bit inefficient (to be precise, its complexity O(n^2)) Multiplication is quite heavy and there is definitely room for improvements. For example, calculating the factorials can be replaced with lookup from pre-build table.

open System

let buildFactorialTable n =
  let rec build v i =
    seq { if i <= n then
            yield (i * v)
            yield! build (i * v) (i + 1) }
  (1 :: (build 1 1 |> Seq.toList)) |> List.toArray

let line (ft : int array) n =
  seq { for k in 0..n do yield (ft.[n] / ((ft.[k]) * (ft.[n-k]))) }

[<EntryPoint>]
let main argv =
  let n = Console.ReadLine() |> int
  let factorialTable = buildFactorialTable n
  for i in 0..(n-1) do
    printfn "%s"  (String.Join (" ", line factorialTable i |> Seq.map string))
  0 // return an integer exit code

Although it also works well, it only can calculate a few lines of the triangle. This is due to fact that factorial grows very quickly.

So the best solution is to generate next line directly from the previous:

open System

let lines n =
  let rec build (prev : int list) i =
    [ if i < n then
        let line = [ yield 1
                     for p in Seq.pairwise prev do
                       yield (fst p) + (snd p)
                     yield 1 ]
        yield line
        yield! build line (i+1) ]
  [ yield [1]; yield! build [1] 1 ]

[<EntryPoint>]
let main argv =
  let n = Console.ReadLine() |> int
  lines n
  |> Seq.iter (fun line -> printfn "%s" (String.Join (" ", line |> Seq.map string)))
  0 // return an integer exit code