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

我被给了一个难题作为礼物。它由4个立方体并排排列组成。每个立方体的面都是四种颜色之一。如何计算F＃中n个序列的笛卡尔乘积？

为了解决这一难题，多维数据集必须定向以使得所有四个立方体上衣是不同的，他们所有的方面都是不同的，他们所有的背上是不同的，他们所有的底部的不同。左侧和右侧并不重要。

我的伪代码的解决方案是：

创建每个立方体的表示。
获取的每个立方体的所有可能的方向（有每个24）。
获取的每个立方体的方向所有可能的组合。
找到满足解决方案的方向的组合。

我解决了使用的F＃是伪代码实现的困扰，但我不能与我所做的第3步的方式satisifed：

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具有我想要的和可行的签名。

然而，使用产品涉及讨厌的线SEQ {屈服Seq.empty}，它unintuitively需要：

值（SEQ <“一个>）
的序列的序列的序列值（SEQ < SEQ <“一个> >）

第二个参数似乎并不的C orrect。

那个奇怪接口由productn很好地隐藏，但是仍然唠叨我不管。

是否有更好，更直观的方式来计算一般n链的笛卡尔积？是否有内置函数（或其组合）可以执行此操作？

来源

2010-07-26 Alex Humphrey

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

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]]}附加到购物车中的每个列表[[3; 4; 5]; [6; 7]]}。这是比赛声明中的第二个条款。

来源

2010-07-26 12:46:20 cfern

+1 - 我觉得这非常符合我试图做的事情的本质。我想唯一的缺点是对列表的依赖，而我的可怕版本与seqs一起工作。 – 2010-07-27 11:04:16

@Alex Humphrey：该算法可以重写为直接使用seq-seqs，但性能会很糟糕。在编写像这样的递归算法时，使用列表自然会出现，因为List的自然事物::剩余结构。您可以轻松地转换您的输入：假设您的输入序列序列被称为'ss'，然后调用'cart1 [for ss in - > Seq.toList s]'。 – cfern 2010-07-27 11:33:17

如果seq超大（假设我有10个其他每个都有1000个方向的形状，并且我使用顺序表达式计算了方向）。由于内存使用情况，不会使用列表最终变得过于禁忌，还是我误解？ – 2010-07-27 11:47:57

这是列表版本的第一次尝试。我认为它可以清理一下。

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-26 19:12:03 TechNeilogy

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

回答

相关问题