recursive_permutation.ml

let insert_all_positions x l = 
let rec aux prev acc l = 
match l with
| [] -> (prev @ [x]) :: acc |> List.rev
| hd::tl as l -> aux (prev @ [hd]) ((prev @ [x] @ l) :: acc) tl 
in aux [] [] l;;


let rec permutation l = 
match l with 
| [] -> []
| hd::[] -> [[hd]]
| hd::tl -> List.fold_left (fun acc p -> acc @ insert_all_positions hd p) [] (permutation tl);;