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

Question

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

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

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

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

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

1. Последовательность значений (seq<'a>)
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

Вот решение 'a list list -> Seq<'a list> вычислить декартово произведение n списков с ленивой оценкой. Я написал это, чтобы быть F# аналогом itertools.product Python

let product lists = 
    let folder list state =
         state |> Seq.allPairs list |> Seq.map List.Cons 
    Seq.singleton List.empty |> List.foldBack folder lists

Это основано на List.allPairs который был введен в F# 4.0.

Answer 3

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

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