Ocaml中的数组操作

我正在尝试在Ocaml中执行Array的所有组合。我想做一个递归函数，recives一个数组，它的初始状态需要为let a = [|0;0;0|]，我需要像第一次迭代那样递归地改变它，需要是a = [|1;0;0|]和下一个a = [|0;1;0|]等等，直到它达到a = [|1;1;1|]所有可能的组合，所以在这种情况下需要做2^3个变化。我知道我不是很明确，但我有点难以解释，但如果有人能帮助我，我会感激。Ocaml中的数组操作

来源

2016-11-11 Funnymemes

你能后至今你已经尝试了什么？ –

-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

来源

2016-11-11 19:31:21

感谢的人，其实我一直在笑 – Funnymemes

好吧@Funnymemes有一个美好的一天。 –

数组是一个可变数据结构，所以如果您要在每次递归调用中对它进行变异，那么就会发生突变。基本上，这意味着，在调用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每次创建一个全新的数组，或者，您可以遍历现有的数组。这样会更有效率，但容易出错。

来源

2016-11-11 15:49:50 ivg

Ocaml中的数组操作

回答

相关问题