permutations.fs

(* insert `thing` into each possible place of a list *)
let rec inserts thing = function
  | [] -> [ [thing] ]
  | (head :: rest) as all -> 
    let normal = thing :: all
    let inserted = List.map (fun n -> head::n) (inserts thing rest)
    normal :: inserted

(* give all possible permutations of a list (does not care about uniqueness of elements) *)
let rec permutations = function
  | [] -> [ [] ] |> Seq.ofList
  | x :: xs ->
    permutations xs
    |> Seq.map (inserts x)
    |> Seq.concat


permutations [1;2;3;4] |> Seq.length // 4! = 24

permutations ["Hi";"Jeff";"how";"are";"you";"today"] |> List.ofSeq

(*
obviously this is crazy, don't force this whole sequence unless you like making your computer generate 10^614 things
just wanted to show that it works for practically infinite sequences and is still fast at the head
*)
permutations [0..300] |> Seq.skip 1000