views:

202

answers:

2

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:

  1. Create a representation of each cube.
  2. Get all the possible orientations of each cube (there are 24 for each).
  3. Get all the possible combinations of orientations of each cube.
  4. 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:

  1. A sequence of values (seq<'a>)
  2. 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?

+3  A: 

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}

Example:

> 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]]

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.

cfern
+1 - I think this pretty much captures the essence of what I'm attempting to do. I guess the only drawback is the dependency on lists, whereas my horrible version works with seqs.
Alex Humphrey
@Alex Humphrey: This algorithm could be rewritten to work with seq-of-seqs directly, but the performance will suck. When writing recursive algorithms like this one, working with lists comes naturally, because of a List's natural something::remaining structure. You can easily convert your input: let's say your input sequence-of-sequences is called `ss`, then call `cart1 [for s in ss -> Seq.toList s]`.
cfern
@cfern: What if the seq is super-massive (imagine I had 10 other shapes which each had 1000 orientations, and I computed the orientations using sequence expressions). Wouldn't using lists eventually become prohibitive because of memory usage, or am I misunderstanding?
Alex Humphrey
Memory usage only matters for the input. If you have 10 shapes with 1000 orientations each, the input will only contain 10^4 items (10 lists of 1000 elements). During the execution of the algorithm intermediate lists are at most 10 elements long. The trick here is that the algorithm outputs the elements on demand (because it's a seq), so it doesn't waste memory generating the result. `cart1 [for _ in 1..10 -> [1..1000]]` works. The algorithm will stack overflow when you have very many (like 10000) input sequences, because it isn't tail-recursive. But such an input doesn't seem very likely.
cfern
@cfern: Thanks for the explanation - I wasn't trying to pick holes, just trying to understand more about the nature of the algorithm. I'm still amazed at how terse that function is :)
Alex Humphrey
A: 

Here's a first try at a list version. I think it could be cleaned up a bit.

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
TechNeilogy

related questions