# 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

• Welcome to Code Review! Good job on your first answer. – SirPython Apr 9 '16 at 23:52
• My code is first try to write something longer than "hello world" in OCaml, so I was happy to see it works :) Thanks for your review! – grigoriytretyakov Apr 11 '16 at 8:46
• Btw, how works "@"? – grigoriytretyakov Apr 11 '16 at 8:49
• "@" concatenates two lists, see pervasives.mli in OCaml library. E.g.: [1; 2] @ [3; 4] → [1; 2; 3; 4] This is not tail-recursive and has complexity O(n) so actually you should use it carefully. – Evgenii Lepikhin Apr 11 '16 at 10:48
• May be Array more suitable in this case, than List? – grigoriytretyakov Apr 11 '16 at 11:30