F # ndaki n dizilerinin kartezyen çarpımını nasıl hesaplayabilirim?

Question

Hediye olarak bir bulmaca verildi. Yan yana düzenlenmiş 4 küpden oluşur. Her küpün yüzleri dört renkten birisidir.

küpler dört küpleri üstleri farklı olduğunu, tüm cepheler farklı şekilde yönlenmesi gerekir bulmacayı çözmek için, tüm sırtlarını farklıdır ve tüm bunların alt en farklı. Sol ve sağ taraflar önemli değil.

Benim sözde kod çözümü oldu:

1. her küpün bir temsilini oluşturun.
2. her küp tüm olası yönelimleri alın (her biri için 24 vardır).
3. her küpün yönelimleri tüm olası kombinasyonlarını alın.
4. çözümü karşılayan yönelimleri kombinasyonunu bulun.

Ben F # o sözde kod bir uygulama kullanarak bulmacayı çözmüş ama 3. adımı yaptım yolu ile satisifed değilim:

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

Yukarıdaki kod çok somut ve sadece işleri olduğu dört yön dizisinin kartezyen ürünü. N dizileri için yazmanın bir yolunu düşünmeye başladım.

I (F # interaktif ince yürütmek gerektiğini şu andan itibaren tüm kod) ile geldi:

// 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 } 

ürün fonksiyonu

seq { yield Seq.empty } 
|> product [ 'a'; 'b'; 'c' ] 
|> product [ 'd'; 'e'; 'f' ] 
|> product [ 'h'; 'i'; 'j' ] 
|> Seq.iter print 

... şöyle kullanılabilir .. Kimin yoluna bakmak ...

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 

Bu tam olarak benim istediğim kullanım. productn, istediğim ve çalıştığım tam imzayı taşıyor.

Ancak, bu ürünü kullanmak aldığı hat seq {verim Seq.empty} içermektedir ve unintuitively alır

: değerleri (DİZİ < 'bir >)

arasında

1. A sekansı sekanslarının bir sekans değerleri (DİZİ < seq < 'bir > >)

ikinci bağımsız görünmüyor c orrect. Garip arayüz productn tarafından güzel gizlidir, ama yine de ne olursa olsun başımın etini olduğu O

.

genel olarak herhangi bir hoş, daha sezgisel yöntemler n sıra kartezyen ürün ihtiyari hesaplamak mı? Bunu yapan yerleşik fonksiyonlar var mı (veya bunların kombinasyonu)?

Answer 1

kullanımı yineleme n listelerinin kartezyen ürün {L1 ..LN}, L1'deki her bir elemanı {L2..LN} listelerinin kartezyen ürünündeki her bir alt listeye eklediğinizde elde ettiğiniz listelerin toplanmasıdır.

let rec cart1 LL = 
    match LL with 
    | [] -> Seq.singleton [] 
    | L::Ls -> seq {for x in L do for xs in cart1 Ls -> x::xs} 

Örnek:

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

kartezyen ürün [1, 2] [3, 4, 5] ve [6, 7] sepetinde her liste için, ekteki 1 {birleşimi olan [[3; 4; 5]; [6; 7]]} ve {2 [4; 5]; [6; 7]]} sepetindeki her bir listeye eklenmiştir. Bu, eşleşme ifadesindeki ikinci maddedir.

Answer 2

İlk önce bir liste sürümünde deneyin. Sanırım biraz temizlenebilir.

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