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

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

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

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

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

Я решил головоломку, используя реализацию этого псевдокода в 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 # interactive):

// 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}, и она неинтуитивно принимает:

Последовательность значений (seq < 'a > )
Последовательность последовательностей значений (seq < ltq < → → )

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

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

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

Ответ 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]]}. Это второе предложение в заявлении соответствия.

Ответ 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