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

Question

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

要解决这个难题，必须调整立方体的方向，使所有四个立方体的顶部都不同，它们的正面都不同，它们的背面都不同，并且它们的底部都不同。左右两边没有关系。

我的伪代码解决方案是:

创建每个的表示
立方体。

获取所有可能的方向
每个立方体(每个立方体有 24 个)。

获取所有可能的组合
每个立方体的方向。

找到方向的组合
这满足解决方案。

我使用 F# 中该伪代码的实现解决了这个难题，但对我执行第 3 步的方式并不满意:

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 }

产品功能可以这样使用......

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>)

第二个论点似乎不正确。

那个奇怪的界面被 productn 很好地隐藏了，但无论如何仍然在唠叨我。

有没有更好、更直观的方法来一般计算 n 个序列的笛卡尔积？是否有任何内置功能(或组合)可以做到这一点？

Answer 1

使用递归: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 附加到购物车 [[3;4;5];[6;7]]} 中每个列表的并集和 {2 附加到购物车 [[3;4;5];[6;7]]} 中的每个列表。这是 match 语句中的第二个子句。