Как вычислить декартово произведение n последовательностей в F #?

Question

Мне предоставили головоломку в подарок. Он состоит из 4 кубов, расположенных бок о бок. Лица каждого куба - один из четырех цветов.

Для решения головоломки кубы должны быть ориентированы так, чтобы все четыре кубика были разными, все их фронты различны, все их спины различны, а все их дно разные. Левая и правая стороны не имеют значения.

Мое решение псевдо-код был:

1. Создать представление каждого куба.
2. Получите все возможные ориентации каждого куба (для каждого из них 24).
3. Получите все возможные комбинации ориентации каждого куба.
4. Найдите комбинацию ориентации , которая удовлетворяет решению.

Я решил загадку, используя реализацию этого псевдо-кода в F #, но я не satisifed с тем, как я сделал шаг 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 имеет именно подпись, которую я хочу и работает.

Однако, используя продукт включает в себя противную линии SEQ {выхода Seq.empty}, и он принимает unintuitively:

1. последовательности значений (SEQ < «в >)
2. Последовательности последовательностей значений (далее < < «Seq в > >)

Второй аргумент не кажется, с дый правильный.

Этот странный интерфейс хорошо спрятан с помощью productn, но по-прежнему воняет мне независимо.

Есть ли более удобные, более интуитивные способы общего вычисления декартова произведения n последовательностей? Есть ли встроенные функции (или комбинация), которые это делают?

Answer 1

Использование рекурсии: декартово произведение n списков {L1 ..LN} - это набор списков, которые вы получаете, когда добавляете каждый элемент в L1 в каждый подсписок в декартовом произведении списков {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} 

Пример:

> 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]]} и {2 прилагаются к каждому списку в корзине [[3; 4; 5]; [6; 7]]}. Это второе предложение в матче.

Answer 2

В первую очередь предлагается версия списка. Я думаю, что его можно немного почистить.

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