Generating permutations in OCaml

open Core.Std;;

let print aofa =
    let s1 = ( Array.length aofa ) - 1 in
    for i = 0 to s1 do
        for j = 0 to (Array.length aofa.(i)) - 1 do
            printf "%d " aofa.(i).(j);
        done;
        printf "\n";
    done;
;;

let rec fact i =
    if i <= 1 then 1 else i * fact (i - 1)
;;

let rec permutations ints =
    let length = Array.length ints in

    if length < 2 then
        [|ints|]
    else begin
        let total = fact length in

        let result = Array.create total (Array.create length 0) in
        for i = 0 to total - 1 do
            result.(i) <- Array.create length 0
        done;

        let block_size = total / length in
        for i = 1 to length do
            let rest = Array.append (Array.sub ints 0 (i - 1)) (Array.sub ints i (length - i)) in
            let rights = permutations rest in
            for r = 0 to (Array.length rights) - 1 do
                let n = Array.append [|Array.get ints (i - 1) |] rights.(r) in
                result.((i - 1) * block_size + r) <- n
            done;
        done;

        result
    end
;;

let () =
    let aofa = permutations [|1; 2; 3|] in
    print aofa;
;;

And result:

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

UPD:

As first step, I wrote naive implementaion on python and then make version in OCaml

def permutations(s):
    if len(s) > 1:
        for i, v in enumerate(s):
            for p in permutations(s[0: i] + s[i+1:]):
                yield [v] + p
    else:
        yield s

def main():
    for p in permutations([1, 2, 3]):
        print(p)

if __name__ == '__main__':
    main()

Your code is totally imperative. In some cases (probably in most) it's faster, but this not the best way to use OCaml :) Here is my solution in functional style:

Printing the list of lists can be done by iterating over list of lists:

let print lst =
List.iter (fun l ->
List.map string_of_int l
|> String.concat " "
|> print_endline
) lst


Next recursive function does:

• Selects head element of the list and makes it heading element of the resulting list

• Recursively calls itself on the list of all previous elements (minus resulting subset) + tail.

let rec permutations result other = function
| [] -> [result]
| hd :: tl ->
let r = permutations (hd :: result) [] (other @ tl) in
if tl <> [] then
r @ permutations result (hd :: other) tl
else
r


All together. Initial result is empty and the stored list of previous elements is also empty:

let () =
permutations [] [] [1; 2; 3]
|> print


StackExchange Code Review Q#125173, answer score: 4