heap_algorithm.ml

let ( |> ) x f = f x;;

let printarray a =   
    let rec printlist = function
        | head :: rest -> print_char head; printlist rest;
        | [] -> print_newline () in 
    
    printlist (Array.to_list a);;
    

let swap a i j = 
    let tmp = Array.get a i in
    Array.set a i (Array.get a j);
    Array.set a j tmp;;


let rec fac n = 
    if n = 0 then 1 else n * fac (n - 1);;

let letters = [|'t'; 'i'; 't'; 'o'; 'u'; 'a'; 'n'|];;
let len = Array.length letters;;

let rec generate k a = 
    if k = 1 then begin
        printarray a
    end else
        for i = 0 to (k - 1) do
            generate (k - 1) a;
            if (k mod 2 <> 0) then
                swap a i (k - 1)
            else
                swap a 0 (k - 1)
        done;;
      
Printf.printf "Number of possibilities: %d\n" (letters |> Array.length |> fac);
generate (Array.length letters) letters;;

print all possibilities of an char array using the naive heap algorithm (pseudo code here https://en.wikipedia.org/wiki/Heap%27s_algorithm)

number of all possible permutation = fac $ length a