¿Cómo calculo el producto cartesiano de n secuencias en F #?

Question

Me dieron un rompecabezas como regalo. Consiste en 4 cubos, dispuestos uno al lado del otro. Las caras de cada cubo son uno de cuatro colores.

Para resolver el rompecabezas, los cubos deben estar orientados de modo que las cuatro partes superiores de los cubos sean diferentes, todos sus frentes sean diferentes, todas sus espaldas sean diferentes y todas sus partes inferiores sean diferentes. Los lados izquierdo y derecho no importan.

Mi solución fue pseudo-código:

1. crear una representación de cada cubo.
2. Obtenga todas las orientaciones posibles de cada cubo (hay 24 para cada uno).
3. Obtenga todas las combinaciones posibles de orientaciones de cada cubo.
4. Encuentra la combinación de orientaciones que satisface la solución.

I resuelto el rompecabezas usando una aplicación de esa pseudo-código en C#, pero no estoy satisfecha con la forma en que hice el paso 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] } 

El código anterior es obra muy concretos, y sólo el producto cartesiano de cuatro secuencias de orientaciones. Empecé a pensar en una forma de escribirlo para n secuencias de orientaciones.

me ocurrió (todo el código a partir de ahora debe ejecutar bien en F # interactiva):

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

La función producto pueda utilizarse como tal ...

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

.. . que conducen a ...

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 

Este es exactamente el uso que quiero. productn tiene exactamente la firma que quiero y funciona.

Sin embargo, utilizando el producto consiste en la SEC línea desagradable {Seq.empty rendimiento}, y unintuitively toma:

1. una secuencia de valores (SEC < 'un >)
2. Una secuencia de secuencias de valores (SEC < seq < 'un > >)

El segundo argumento no parece c orrect.

Esa extraña interfaz está oculta muy bien por productn, pero aún así me persigue.

¿Existen formas más agradables e intuitivas de calcular genéricamente el producto cartesiano de n secuencias? ¿Hay alguna función incorporada (o combinación de) que haga esto?

Answer 1

Uso recursión: el producto cartesiano de n listas {L1 ..LN} es la colección de listas que obtienes al agregar cada elemento en L1 a cada sublista en el producto cartesiano de las listas {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} 

Ejemplo:

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

el producto cartesiano de [1; 2] [3; 4; 5] y [6; 7] es la unión de {1 anexa a cada lista en el carrito [[3; 4; 5]; [6; 7]]} y {2 añadidos a cada lista en el carro [[3; 4; 5]; [6; 7]]}. Esta es la segunda cláusula en la declaración del partido.

Answer 2

Aquí hay un primer intento en una versión de la lista. Creo que podría limpiarse un poco.

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