14

我收到了一个谜题作为礼物。它由 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# 交互中正常执行）：

// 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 }，它不直观地采用：

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

第二个论点似乎不正确。

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

Are there any nicer, more intuitive ways to generically compute the cartesian product of n sequences? Are there any built in functions (or combination of) that do this?

4

3 回答 3

12

Use recursion: the cartesian product of n lists {L1..LN} is the collection of lists you get when you add each element in L1 to each sublist in the cartesian product of lists {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}

Example:

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

The cartesian product of [1;2] [3;4;5] and [6;7] is the union of {1 appended to each list in cart [[3;4;5];[6;7]]} and {2 appended to each list in cart [[3;4;5];[6;7]]}. This is the second clause in the match statement.

于 2010-07-26T12:46:20.580 回答
1

Here's a solution 'a list list -> Seq<'a list> to calculate the Cartesian product of n lists, with lazy evaluation. I wrote it to be an F# analogue of Python's itertools.product 

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

It's based on List.allPairs which was introduced in F# 4.0.

于 2018-05-12T13:53:35.480 回答
0

Here's a first try at a list version. I think it could be cleaned up a bit.

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
于 2010-07-26T19:12:03.653 回答