Как вычислить декартово произведение 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]]}.Это второе предложение в выражении match.

Answer 2

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

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