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

Question

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

为了解决难题,立方体必须定向,以便所有四个立方体的顶部不同,它们的所有前沿都不同,它们的背部都是不同的,并且它们的底部都是不同的.左右两边无所谓.

我的伪代码解决方案是:

1. 创建每个多维数据集的表示.
2. 获取每个立方体的所有可能方向(每个方块有24个).
3. 获取每个立方体的所有可能的方向组合.
4. 找到满足解决方案的方向组合.

我使用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#interactive中执行得很好):

// 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具有我想要和签名的签名.

但是,使用产品涉及令人讨厌的行seq {yield Seq.empty},它不直观地采取:

1. 一系列值(seq <'a>)
2. 一系列值序列(seq <seq <'a >>)

第二个论点似乎不正确.

这个奇怪的界面被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; 4; 5]; [6; 7]中每个列表附加的{1的并集}并且{2附加到购物车中的每个列表[[3; 4; 5]; [6; 7]]}.这是match语句中的第二个子句.