Ocamlでの配列操作

Question

Ocamlで配列のすべての組み合わせを実行しようとしています。 配列を受け取り、その初期状態が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を使用すると、毎回新しく新しい配列を作成することができます。あるいは、既存の配列を反復するだけで済みます。これはより効率的ですが、エラーが発生しやすくなります。