Skip to content

Instantly share code, notes, and snippets.

@MassD
Last active November 27, 2023 04:10
Show Gist options
  • Save MassD/fa79de3a5ee88c9c5a8e to your computer and use it in GitHub Desktop.
Save MassD/fa79de3a5ee88c9c5a8e to your computer and use it in GitHub Desktop.
A implementation for generating all permutations of a list, written in OCaml
(* note that in order to preserve certain order
and also show the conciseness of the implementation,
no tail-recursive is used *)
let ins_all_positions x l =
let rec aux prev acc = function
| [] -> (prev @ [x]) :: acc |> List.rev
| hd::tl as l -> aux (prev @ [hd]) ((prev @ [x] @ l) :: acc) tl
in
aux [] [] l
let rec permutations = function
| [] -> []
| x::[] -> [[x]] (* we must specify this edge case *)
| x::xs -> List.fold_left (fun acc p -> acc @ ins_all_positions x p ) [] (permutations xs)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment