我正在尝试在 Ocaml 中执行数组的所有组合。
我正在尝试执行一个递归函数来接收数组,其初始状态需要为 let a = [|0;0;0|]
并且我需要像第一次迭代一样递归地更改它需要是 a = [|1;0;0|]
和下一个 a = [|0;1;0|]
等等,直到达到 a = [|1;1;1|]
进行所有可能的组合,因此在这种情况下需要进行 2^3 次更改。
我知道我不是很明确,但对我来说解释起来有点困难,但如果有人可以帮助我,我将不胜感激。
最佳答案
数组是一种可变的数据结构,因此如果您要在每次递归调用中对其进行变异,那么变异就会发生。基本上,这意味着,在 2^3
调用之后,数组的状态将是最后的组合。所以,这样做根本没有意义。一个有效的解决方案是创建一个函数,该函数将采用一个初始数组,并返回所有组合的列表。更有效的解决方案是编写一个函数,该函数将采用另一个函数,并将其应用于所有组合(或折叠所有组合)。这将允许您节省内存,因为您不需要存储所有组合。
概要是实现以下接口(interface):
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 每次创建一个全新的数组,或者,您也可以只迭代现有的数组。这会更有效,但容易出错。
关于arrays - Ocaml 中的数组操作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40550000/