Разработка на коленке

"тут должна быть красивая цитата о программировании"

Перестановки элементов массива на OCaml

2016-04-08 20:00

Написал свою реализацию поиска всех перестановок на OCaml. Код отправил на код-ревью [ссылка], посмотрю, что скажут.

Пока писал, сломал себе голову. Многие вещи в 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;
;;

Результат такой:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
comments powered by Disqus