首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >笛卡尔乘积(复杂性改进)

笛卡尔乘积(复杂性改进)
EN

Stack Overflow用户
提问于 2018-06-02 17:33:55
回答 2查看 232关注 0票数 0

我想写一个函数,给出两个序列的cartesiant乘积,这就是我所做的,但我认为它可能很有趣,因为我想使用s1浏览第一个序列一次,并使用map浏览第二个序列n次,然后附加所有结果:

代码语言:javascript
复制
`let cartesian_product a b =
    let na = length a in
    let nb = length b in
    init
    (na * nb)
    (fun j -> let i = j / nb in
      at a i, at b (j - i*nb))
`

这就是我当时所做的:

代码语言:javascript
复制
`let rec cartesian_product a b =
 let rec aux x b () = match b () with
  | Nil -> Nil
  | Cons(e, b) -> Cons ((x, e), aux x b)
 in
 match a () with
 | Nil -> nil
 | Cons (x, a)  -> append (aux x b) (cartesian_product a b)`

但是我没有使用map (有没有更好的方法)??

EN

回答 2

Stack Overflow用户

发布于 2018-06-02 18:40:34

您的aux函数本质上是map的一个特例,因此您可以这样写:

代码语言:javascript
复制
let rec cartesian_product a b = match a () with
  | Nil -> Nil
  | Cons (x, a)  -> append (map (fun e -> (x, e)) b) (cartesian_product a b)

经验法则是,当您觉得需要编写一个名为aux的函数时,请后退一步,考虑是否可以使用mapfold。实际上,您可以通过使用fold而不是自己解构序列来改进我的代码。

票数 1
EN

Stack Overflow用户

发布于 2018-06-04 18:26:57

下面是一个结构为list的算法示例:

代码语言:javascript
复制
let cartesian_product a b =
  let open List in
  let mk_tuple l n = map (fun x -> (n,x)) l in  
   a |> map (mk_tuple b) |> fold_left append []

这将为您提供:

代码语言:javascript
复制
    cartesian_product [0;1] [2;3];;
    - : (int * int) list = [(0, 2); (0, 3); (1, 2); (1, 3)]
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/50655463

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档