问Ocaml中的数组操作
EN

Stack Overflow用户

提问于 2016-11-11 06:24:12

回答 2查看 804关注 0票数 2

我试图在Ocaml中完成数组的所有组合。我正在尝试执行一个递归函数，它接收一个数组，它的初始状态需要是let a = [|0;0;0|]，我需要递归地更改它，就像在第一次迭代中，需要是a = [|1;0;0|]，下一个a = [|0;1;0|]等等，直到它到达a = [|1;1;1|]，完成所有可能的组合，所以在本例中需要做2^3的更改。我知道我不是很明确，但我有点难以解释，但如果有人能帮助我，我将不胜感激。

arrays

ocaml

combinatorics

性能强劲，每月20元起的MySQL

功能完善，便宜稳定，没有业务可以自动停机，强效降本的MySQL

回答 2

Stack Overflow用户

回答已采纳

发布于 2016-11-11 11:31:21

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

票数 0

Stack Overflow用户

发布于 2016-11-11 07:49:50

数组是一个可变的数据结构，所以如果您要在每个递归调用中对它进行变异，那么就会进行突变。基本上，这意味着，在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-th位(元素)可以被确定为state land (1 lsl n)。您可以每次使用Array.init来创建一个新的数组，或者，只需在现有数组上迭代即可。这将更有效率，但容易出错。