Массирование массивов в Ocaml

Question

Я пытаюсь выполнить все комбинации массива в Окамле. Я пытаюсь сделать рекурсивную функцию, которая возвращает массив, и его начальное состояние должно быть let a = [|0;0;0|], и мне нужно его рекурсивно менять, так как в первой итерации должно быть a = [|1;0;0|], а следующее a = [|0;1;0|] и так далее, пока оно не достигнет a = [|1;1;1|]. все возможные комбинации, поэтому в этом случае необходимо сделать 2^3 изменения. Я знаю, что я не был очень явным, но его немного сложно объяснить, но если бы кто-то мог мне помочь, я был бы благодарен.

Answer 1

let combinaison f n = 
    let rec aux acc n = 
    if n=0 then List.iter f acc 
    else (
     aux (List.map (fun l -> 0::l ) acc) (n-1); 
     aux (List.map (fun l -> 1::l ) acc) (n-1); 
    ) 
    in 
    aux [[]] n 
;; 

Тест

combinaison (fun lx -> 
    let a=Array.of_list lx in 
    Array.iter (fun x -> 
    Printf.printf "%d " x 
) a ; 
    Printf.printf "\n" 
) 3;; 

0 0 0 
1 0 0 
0 1 0 
1 1 0 
0 0 1 
1 0 1 
0 1 1 
1 1 1 

Answer 2

Массив - изменяемая структура данных, поэтому, если вы собираетесь мутировать его во всех рекурсивных вызовах, то мутация будет принята на свои места. В принципе, это означает, что после вызовов 2^3 состояние массива будет последней комбинацией. Таким образом, нет никакого смысла делать это вообще. Допустимым решением было бы создать функцию, которая примет начальный массив и вернет список всех комбинаций. Еще более эффективное решение состоит в том, чтобы написать функцию, которая возьмет другую функцию и применит ее ко всем комбинациям (или сбрасывает все комбинации). Это позволит вам сохранить память, так как вам не нужно сохранять все комбинации.

Схема будет реализовать следующий интерфейс:

type state 
val zero : state 
val next : state -> state option 
val value : state -> int array 

Где государство будет курсор, который будет двигаться через пространство комбинаций. Это может быть целочисленный или целочисленный массив или что-то еще. После того, как эти функции реализованы вы можете легко реализовать функцию следующим образом:

let fold_combinations f init = 
    let rec fold state x = 
    let x = f (value state) x in 
    match next state with 
    | None -> x 
    | Some state -> fold state x in 
    fold zero init 

Наконец, ваш пример не показывает все возможные комбинации или перестановки, но все возможных двоичных значения битовой ширины, равную длину входного массива. Если это действительно задача, которую вы пытаетесь решить, вы можете просто перевести целое число в двоичное представление. В этом случае хорошим выбором для state будет int, а затем next функция - это приращение, которое остановится на 2^k-1, где k - это длина начального состояния. А функция value просто преобразует целое число в массив бит, где n-й бит (элемент) может быть определен как state land (1 lsl n). Вы можете использовать Array.init для создания нового нового массива каждый раз, в качестве альтернативы вы можете просто перебирать существующий массив. Это будет более эффективным, но подверженным ошибкам.