如何在F#中计算n个序列的笛卡尔积？

Question

如何在F#中计算n个序列的笛卡尔积？

f#puzzlecartesian-product

14

我收到了一个谜题作为礼物，它由四个正方体组成，排成一排。每个立方体的面都是四种颜色之一。

为了解决这个谜题，必须将正方体定向，以使所有四个正方体的顶部不同，所有正方体的前面、后面和底部也不同。左侧和右侧不重要。

我的伪代码解决方案是：

1. 创建每个正方体的表示。 2. 获取每个正方体的所有可能的定向（每个正方体有24个）。 3. 获取每个正方体定向的所有可能组合。 4. 找到满足解决方案的定向组合。

我使用F#中该伪代码的实现解决了这个谜题，但对我完成第三步的方式不太满意。

let problemSpace =
    seq { for c1 in cube1Orientations do
              for c2 in cube2Orientations do
                  for c3 in cube3Orientations do
                      for c4 in cube4Orientations do
                          yield [c1; c2; c3; c4] }

上面的代码非常具体，仅计算了四个方向序列的笛卡尔积。我开始思考如何编写可以处理n个方向序列的代码。

我想到了以下代码（从现在开始的所有代码都应该可以在F#互动环境中正常执行）：

// Used to just print the contents of a list.
let print = 
    Seq.fold (fun s i -> s + i.ToString()) "" >> printfn "%s"

// Computes the product of two sequences - kind of; the 2nd argument is weird.
let product (seq1:'a seq) (seq2:'a seq seq) =
    seq { for item1 in seq1 do
              for item2 in seq2 do
                  yield item1 |> Seq.singleton |> Seq.append item2 }

product 函数可以这样使用...

seq { yield Seq.empty }
|> product [ 'a'; 'b'; 'c' ]
|> product [ 'd'; 'e'; 'f' ]
|> product [ 'h'; 'i'; 'j' ]
|> Seq.iter print

...导致...

let productn (s:seq<#seq<'a>>) =
    s |> Seq.fold (fun r s -> r |> product s) (seq { yield Seq.empty })

[ [ 'a'; 'b'; 'c' ]
  [ 'd'; 'e'; 'f' ]
  [ 'h'; 'i'; 'j' ] ]
|> productn
|> Seq.iter print

这正是我想要的用法。 productn 恰好具有我想要的签名，而且可行。

然而，使用 product 就需要那个讨厌的代码行 seq { yield Seq.empty }，并且它（以不直观的方式）接受：

值序列 (seq<'a>)
值序列 的序列 (seq<seq<'a>>)

第二个参数看起来不正确。

那个奇怪的接口虽然被 productn 很好地隐藏了，但仍然会让我感到烦恼。

有没有更好、更直观的方法来通用地计算 n 个序列的笛卡尔积？是否有任何内置函数（或组合函数）可以做到这一点？

- Alex Humphrey

3个回答

1

这里有一个解决方案'a list list -> Seq<'a list>，用于计算n个列表的笛卡尔积，使用惰性评估。我编写它是为了成为Python itertools.product的F#类比。

let product lists = 
    let folder list state =
         state |> Seq.allPairs list |> Seq.map List.Cons 
    Seq.singleton List.empty |> List.foldBack folder lists

它基于在F# 4.0中引入的List.allPairs。

- Colonel Panic

0

这是第一次尝试列表版本。我认为它需要稍微整理一下。

let rec cart nll = 
  let f0 n nll =
    match nll with
    | [] -> [[n]]
    | _ -> List.map (fun nl->n::nl) nll
  match nll with
  | [] -> []
  | h::t -> List.collect (fun n->f0 n (cart t)) h

- TechNeilogy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cfern · Accepted Answer

使用递归：n个列表L1到LN的笛卡尔积是当你将L1中的每个元素添加到列表{L2..LN}的笛卡尔积的每个子列表时得到的列表集合。

let rec cart1 LL = 
    match LL with
    | [] -> Seq.singleton []
    | L::Ls -> seq {for x in L do for xs in cart1 Ls -> x::xs}

示例：

> cart1 [[1;2];[3;4;5];[6;7]] |> Seq.toList;;
val it : int list list =
  [[1; 3; 6]; [1; 3; 7]; [1; 4; 6]; [1; 4; 7]; [1; 5; 6]; [1; 5; 7]; [2; 3; 6];
   [2; 3; 7]; [2; 4; 6]; [2; 4; 7]; [2; 5; 6]; [2; 5; 7]]

[1;2] [3;4;5] 和 [6;7] 的笛卡尔积是由 {将 1 追加到 cart [[3;4;5];[6;7]] 中的每个列表中} 和 {将 2 追加到 cart [[3;4;5];[6;7]] 中的每个列表中} 组成的并集。这是匹配语句中的第二个子句。