permutation.ml

let pickout xs index =
  let (_, opt, rest) =
    List.fold_left
    (fun (i, opt, rest) x ->
      if i = index then (i + 1, Some x, rest)
      else (i + 1, opt, x::rest)) (0, None, []) xs
  in
  match opt with
  | None -> failwith "not found"
  | Some x -> (x, rest)

let rec perm acc result = function
  | [] -> acc::result
  | rest ->
      let rec iter i result =
        if i >= List.length rest then result
        else begin
          let (x, xs) = pickout rest i in
          let result = perm (x::acc) result xs in
          iter (i + 1) result
        end
      in
      iter 0 result

let () =
  let ll = perm [] [] [1;2;3;4] in
  List.iter
  (fun l -> List.iter (fun x -> Printf.printf "%d " x) l;
    print_newline ()) ll