chess960 in OCaml — Permutations

let rec permutations lst = 
  let rec insert x l = match l with
    | [] -> [[x]]
    | a::m -> (x::l) :: (List.map (fun y -> a::y) (insert x m))
  in
    match lst with
      | a::m -> List.flatten (List.map (insert a) (permutations m))
      | _ -> [lst]

type piece = R | N | B | Q | K
    

Lists of Pieces and their Permutations

# [R;N;B;Q;K;B;N;R];;
- : piece list = [R; N; B; Q; K; B; N; R]
# let perms = permutations [R;N;B;Q;K;B;N;R];;
val perms : piece list list =
  [[R; N; B; Q; K; B; N; R]; [N; R; B; Q; K; B; N; R];
   [N; B; R; Q; K; B; N; R]; [N; B; Q; R; K; B; N; R];
   [N; B; Q; K; R; B; N; R]; [N; B; Q; K; B; R; N; R];
   [N; B; Q; K; B; N; R; R]; [N; B; Q; K; B; N; R; R];
   [R; B; N; Q; K; B; N; R]; [B; R; N; Q; K; B; N; R];
   [B; N; R; Q; K; B; N; R]; [B; N; Q; R; K; B; N; R];
   [B; N; Q; K; R; B; N; R]; [B; N; Q; K; B; R; N; R];
   [B; N; Q; K; B; N; R; R]; [B; N; Q; K; B; N; R; R];
   [R; B; Q; N; K; B; N; R]; [B; R; Q; N; K; B; N; R];
   [B; Q; R; N; K; B; N; R]; [B; Q; N; R; K; B; N; R];
   [B; Q; N; K; R; B; N; R]; [B; Q; N; K; B; R; N; R];
   [B; Q; N; K; B; N; R; R]; [B; Q; N; K; B; N; R; R];
   [R; B; Q; K; N; B; N; R]; [B; R; Q; K; N; B; N; R];
   [B; Q; R; K; N; B; N; R]; [B; Q; K; R; N; B; N; R];
   [B; Q; K; N; R; B; N; R]; [B; Q; K; N; B; R; N; R];
   [B; Q; K; N; B; N; R; R]; [B; Q; K; N; B; N; R; R];
   [R; B; Q; K; B; N; N; R]; [B; ...]; ...]
# length perms;;
- : int = 40320
# let rec factorial n = if n = 1 then n else n * (factorial (n-1));;
val factorial : int -> int = <fun>
# factorial 8;;
- : int = 40320
#