The ideal way to write permutation function in OCaml

Question

Given a list, and output a list of all its permutations.

Here is my thinking:

Recursively, a permutation of hd::tl is to distribute hd into each list of the permutations of tl. By distributing hd, I mean inserting hd into every possible slot among the list.

For example, distributing 1 into [2;3] generates [[1;2;3];[2;1;3];[2;3;1]].

So here is the code

let distribute c l =
  let rec insert acc1 acc2 = function
    | [] -> acc2
    | hd::tl ->
      insert (hd::acc1) ((List.rev_append acc1 (hd::c::tl)) :: acc2) tl
  in 
  insert [] [c::l] l

let rec permutation = function
  | [] -> [[]]
  | hd::tl -> 
    List.fold_left (fun acc x -> List.rev_append (distribute hd x) acc) [] (permutation tl)

---

I guess the above code is correct.

My question is: is there any better way (in terms of simplicity, performance, space efficiency, etc) to write permutations in OCaml?

Answer 1

Other approaches include a) for each element, prepend it to each of the permutations of the list excluding the element, or b) generate permutations from each of the n! indices. See the Rosetta Code examples. I suspect these have similar space complexities.