4
\$\begingroup\$
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()
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Good job on your first answer. \$\endgroup\$ – SirPython Apr 9 '16 at 23:52
  • \$\begingroup\$ 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! \$\endgroup\$ – grigoriytretyakov Apr 11 '16 at 8:46
  • \$\begingroup\$ Btw, how works "@"? \$\endgroup\$ – grigoriytretyakov Apr 11 '16 at 8:49
  • \$\begingroup\$ "@" 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. \$\endgroup\$ – Evgenii Lepikhin Apr 11 '16 at 10:48
  • \$\begingroup\$ May be Array more suitable in this case, than List? \$\endgroup\$ – grigoriytretyakov Apr 11 '16 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.