如何計算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個序列的笛卡爾乘積？

回答

相關問題