Permutations

let length = Seq.length

let take = Seq.take

let skip = Seq.skip

let (++) = Seq.append

let concat = Seq.concat

let map = Seq.map

let (|Empty|Cons|) (xs:seq<'a>) : Choice<Unit, 'a * seq<'a>> =

    if (Seq.isEmpty xs) then Empty else Cons(Seq.head xs, Seq.skip 1 xs)

let interleave x ys =

    seq { for i in [0..length ys] ->

            (take i ys) ++ seq [x] ++ (skip i ys) }

let rec permutations xs =

            match xs with

            | Empty -> seq [seq []]

            | Cons(x,xs) -> concat(map (interleave x) (permutations xs))