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:
- 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.
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] }
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.
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
... which lead to ...
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
This is exactly the usage I want. productn has exactly the signature I want and works.
However, using product involves the nasty line seq { yield Seq.empty }, and it unintuitively takes:
- A sequence of values (seq<'a>)
- A sequence of sequences of values (seq<seq<'a>>)
The second argument doesn't seem correct.
That strange interface is hidden nicely by productn, but is still nagging me regardless.
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?