How do I compute the cartesian product of n sequences in F#?

how to find cartesian product
cartesian product of a set with itself
cartesian product of three sets
cartesian product discrete math
cartesian product with empty set
cartesian product python
cartesian product vs cross product
cartesian product symbol

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?

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.

Algebraic and Differential Topology of Robust Stability, From Subsection 13.2.7, it follows that, to compute the homology of Dx Q in such as 14.7.1 Twisted Cartesian Product Spectral Sequence We filter C(N × F) as  cartesian product , seq This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub .

Here's a solution 'a list list -> Seq<'a list> to calculate the Cartesian product of n lists, with lazy evaluation. I wrote it to be an F# analogue of Python's 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

It's based on List.allPairs which was introduced in F# 4.0.

Bordism, Stable Homotopy, and Adams Spectral Sequences, That is, given [M",e,g] and [N", f, h] we can assume that e : M" '—> A and f : N" ~'—​> A with e(M") fif(N") = lb. Define then Q? is a graded ring with the operation of multiplication given by the Cartesian product. Then we compute Of for k = 0, 1. Cartesian Product of Lists in F# A problem came up on stackoverflow: how to compute the Cartesian product of several sequences in F# ? The poster wanted a solution involving sequences, presumably to meet external requirements, so my solution below using lists wasn’t quite right.

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

Vector Measures, For each n we find an index p, such that Af.0/0). (t) = f(t), for t e U B. n = 1 n- oo For each n we take a 9-step function g, equal to f.p., Let (E) be a sequence of metrizable spaces, E = TIE, their cartesian product and F a metrizable space. Cartesian product of n lists. Cartesian product of a variable number of lists. Input is a list of lists of which the cartesian product is to be constructed; output is a list that contains the elements of the product set, as lists. val cartesian : lstlst:'a list list -> 'a list list.

Cartesian Product of Sequences, Computes the Cartesian product of a sequence of sequences. product of a sequence of sequences. let rec cartSeq (nss:seq<#seq<'a>>) = let f0 (n:'a)  You can indeed create a cartesian product without recursion. What you need is to use the enumerator. I used a non-generic enumerator to work with any types.

Cartesian Product, Cartesian Product Definition for Multiplication of Whole Numbers. Let A and B be two finite sets with a = n(A) and b = n(B)  This is still a correct result if you consider a cartesian product to be a set, which is an unordered collection. Note that the set elements are still ordered lists. A cartesian product is an unordered collection of ordered collections. It draws attention though to the gloss of using list representations as sets.

Cartesian product, In mathematics, specifically set theory, the Cartesian product of two sets A and B, denoted A × B One can similarly define the Cartesian product of n sets, also known as an n-fold Cartesian the natural numbers: this Cartesian product is the set of all infinite sequences with the ith term in its {\displaystyle (f\times g)(a,x)=(​. One can show that the vector produced by a cross product of two vectors × is orthogonal to both and . To do so, compute the dot products. These products are called triple products - since the operation on the outside is a dot product, these are the scalar triple products.

Comments
  • +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: 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].
  • 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?
  • 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.
  • 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 :)