POJ 3187 Backward Digit Sums

gistfile1.fs

let [| n; sum |] = System.Console.ReadLine().Split([|' '|]) |> Array.map int

let rec permutations list taken = 
  seq { if Set.count taken = List.length list then yield [] else
        for l in list do
          if not (Set.contains l taken) then 
            for perm in permutations list (Set.add l taken)  do
              yield l::perm }

let step xs = seq {
  for (x, y) in Seq.zip (Seq.take (Seq.length xs - 1) xs) (Seq.skip 1 xs) do
      yield x + y
}

let toInt xs =
  let mutable ans = step xs
  while Seq.length ans <> 1 do
    ans <- step ans
  Seq.head ans

permutations [1..n] Set.empty
|> Seq.filter (fun x -> toInt x = sum)
|> Seq.head
|> printfn "%A"