Heap's algorithm

permute_arr.ml

let generate (a : int array) : int array list =
  let acc = ref [] in
  let swap a i j = let tmp = a.(i) in a.(i) <- a.(j); a.(j) <- tmp in
  let rec generate' (k : int) (a : int array) =
   match k with
   | 1 -> acc := (Array.copy a) :: !acc
   | _ ->
    for i=0 to pred k do
      generate' (k - 1) a;
      match k mod 2 with
      | 0 -> swap a i (k - 1)
      | _ -> swap a 0 (k - 1)
    done in 
  generate' (Array.length a) a;
  !acc;;

(* INPUT : generate [| 1; 2; 3 |];;
OUTPUT : [[|3; 2; 1|]; [|2; 3; 1|]; [|1; 3; 2|]; [|3; 1; 2|]; [|2; 1; 3|]; [|1; 2; 3|]]
*)