如何计算F#中n个序列的笛卡尔积? [英] How do I compute the cartesian product of n sequences in F#?
问题描述
作为礼物，我感到困惑.它由4个并排排列的立方体组成.每个立方体的面都是四种颜色之一.
I was given a puzzle as a present. It consists of 4 cubes, arranged side by side. The faces of each cube are one of four colours.
要解决这个难题，必须对多维数据集进行定向，以使所有四个多维数据集的顶部都不同，它们的正面都不同，背面都不同，底部都不同.左右两侧都没关系.
To solve the puzzle, the cubes must be orientated so that all four cubes' tops are different, all their fronts are different, all their backs are different and all their bottom's are different. The left and right sides do not matter.
我的伪代码解决方案是:
My pseudo-code solution was:
- 为每一个创建一个表示 立方体.
- 获取所有可能的方向 每个立方体(每个有24个).
- 获取以下所有可能的组合 每个立方体的方向.
- 找到方向的组合 满足解决方案的要求.
- Create a representation of each cube.
- Get all the possible orientations of each cube (there are 24 for each).
- Get all the possible combinations of orientations of each cube.
- Find the combination of orientations that satisfies the solution.
我使用F#中的伪代码实现解决了这个难题，但是我对第3步的方式不满意.
I solved the puzzle using an implementation of that pseudo-code in F#, but am not satisifed with the way I did step 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个方向序列编写它的方法.
The above code is very concrete, and only works out the cartesian product of four sequences of orientations. I started thinking about a way to write it for n sequences of orientations.
我想出了(从现在开始，所有代码都应在F#交互中很好地执行):
I came up with (all the code from now on should execute fine in 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 }
产品功能可以这样使用...
The product function could be used like so...
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完全具有我想要的签名并且可以使用.
This is exactly the usage I want. productn has exactly the signature I want and works.
但是，使用产品涉及讨厌的行seq {yield Seq.empty}，并且直观地得出:
However, using product involves the nasty line seq { yield Seq.empty }, and it unintuitively takes:
- 一系列值(seq<'a>)
- 值(seq< seq< a>>)的序列的序列
第二个参数似乎不正确.
The second argument doesn't seem correct.
productn很好地隐藏了这个奇怪的界面，但是无论如何仍在困扰我.
That strange interface is hidden nicely by productn, but is still nagging me regardless.
是否有更好，更直观的方法来一般性地计算n个序列的笛卡尔积?有内置的功能(或组合功能)吗?
Are there any nicer, more intuitive ways to generically compute the cartesian product of n sequences? Are there any built in functions (or combination of) that do this?
推荐答案
使用递归:n个列表{L1..LN}的笛卡尔积是将L1中的每个元素添加到列表中的每个子列表时所获得的列表的集合.列表{L2..LN}的笛卡尔积.
Use recursion: the cartesian product of n lists {L1..LN} is the collection of lists you get when you add each element in L1 to each sublist in the cartesian product of lists {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语句中的第二个子句.
The cartesian product of [1;2] [3;4;5] and [6;7] is the union of {1 appended to each list in cart [[3;4;5];[6;7]]} and {2 appended to each list in cart [[3;4;5];[6;7]]}. This is the second clause in the match statement.
这篇关于如何计算F#中n个序列的笛卡尔积?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
