Adding a method for computing Cartesian Product to Groovy’s Collection(s)

In these days I’m using the Groovy programming language very often, I found this language very intuitive and expressive. I try to use, when it is appropriate and convenient , Functional programming style and methods.

One of the key elements of functional programming paradigm (opposite to the imperative paradigm) is “thinking in  space rather than thinking in time”, this translates in a extensive usage of collections and constructs for creating a collection based on existing collections. The most common collection used is the list, the syntactic construct for creating a list based on existing lists is named List comprehension.

I think that the list, or more generic collection, comprehension in Groovy is very powerful (Groovy Collection API), and in my everyday usage I found that it has everything that I need to express the algorithm that I implement in terms of Collection comprehension. By the way, more that once I needed to obtain the Cartesian product of two collections, so I thought it is nice to have a method in Collection for computing the Cartesian product.

Cartesian product

The Cartesian product is a mathematical operation which returns a set (or product set) from multiple sets. That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs (a,b) where a ∈ A and b ∈ B:

.

A very common example of the Cartesian product is the deck of playing cards: in a standard 52-card deck the ranks form a 13-element set {‘ace’, 2, 3, 4, 5, 6, 7, 8, 9, 10, ‘jack’, ‘queen’, ‘king’}, and the suits form a 4-element set {‘spades’, ‘hearts’, ‘diamonds’, ‘clubs’}; the deck is the Cartesian product between the ranks and the suits: deck = suits × ranks ={(‘ace’, ‘spades’), (2, ‘spades’), (3,’spades’), …, (‘king’, ‘clubs’)}.

The Cartesian  product can be used to implement the Polynomial expansion; to multiply two factors, each term of the first factor must be multiplied by each term of the other factor:

Each factor can be stored in a list (where each element of the list is a term of the factor); once obtained the set containing the Cartesian product of the two lists it is enough to multiply the elements of each pair and sum the results:

def p1 = ['a', 'b', 'c']
def p2 = ['x', 'y']
def p1_x_p2 = cartesianProduct(p1, p2).collect{"${it[0]}*${it[1]}"}.join(" + ")

Result: a*x + a*y + b*x + b*y + c*x + c*y

Implementation

A simple way to implement the Cartesian product in Groovy is to define a function that has the two collections as parameters and returns a new list containing all the pairs.

def cartesianProduct(A, B) {
  []
}

In the first attempt to implement the body of this function we can create a new list that will store the output and then implement a nested loop, where the outer loop (a) iterate over the elements first collection and the inner loop (b) iterate on the elements of the second collections; at each step in the inner loop we insert in the list a pair made by the element a of the first collection and the element b of the second collection:

def cartesianProduct1(A, B) {
  def result = []
  for(def a = 0; a < A.size(); a++) {
    for(def b = 0; b < B.size(); b++) {       result.add([A[a], B[b]])     }   }   return result } 

The previous implementation works correctly but it doesn’t have a Groovy style, in fact it is implemented in a very imperative style. Replacing the two “for” loops with the “each” method of the List is a first attempt for masking the imperative style, by the way in my opinion it doesn’t really change the substance: we still have two nested loop and we build the result iteratively:

 def cartesianProduct2(A, B) {   def result = []   A.each{a->
    B.each{b->
      result.add([a, b])
    }
  }
  return result
}

We can do better, we are not interested in code that just works, aren’t we?

The inner loop can be seen as a “mapping” functions of the set B, where each element b of B is mapped by the pair [a, b]:

.

In this way we can implement the Cartesian product with a single loop on the elements a of first collection: in each step of the loop we concatenate to the result collection the partial result obtained using the previous mapping. For implementing this mapping function we can use the “collect()” method of the Groovy’s Collection which iterates through the collection transforming each entry into a new value using the given closure.

def cartesianProduct3(A, B) {
  def result = []
  A.each{a->
    result += B.collect{b->[a, b]}
  }
  return result
}

In the same way it is possible to replace the remaining loop with a mapping function: to each element a of A we map the result of g(a, B) as in:

.

In this case the mapping is “one-to-many”, that is to each elements of A we map a set. In this case we cannot use the “collect()” method of the list, if we used collect the result would be a list containing various sub-lists (as many as the number of elements of A). What we need is a method that concatenates the result of the mapping, this method is “collectMany()“:

def cartesianProduct4(A, B) {
  A.collectMany{a->B.collect{b->[a, b]}}
}

The final step is to add this functionality as a method of the Collection(s), Groovy has the functionality to create at run time new methods for any class, this technique is known in the Groovy’s world as ExpandoMetaClass. Using the ExpandoMetaClass creating a new method for any class (even if the class is part of the JDK, GDK or a third party library) is easy as creating a new Closure and insert it in the metaClass of the class as in:

class A {
  def content
}
A.metaClass.printContent = {->
  println content
}
new A(content: 'test content').printContent()

Result: test content
In the same way we can add the cartesianProduct to the Collection class:

java.util.Collection.metaClass.cartesianProduct = {B->
assert B instanceof java.util.AbstractCollection
if(size() == 0 || B.size() == 0) []
else collectMany{a->B.collect{b->[a, b]}}
}

In the final code it is checked if one of the two Collection it is empty, in that case the result is an empty list.

Since the method is added to the Collection class it is possible to use it for any derived class, such as any list or range:

(('a'..'c').cartesianProduct(('x'..'y')))

Result: [[‘a’, ‘x’], [‘a’, ‘y’], [‘b’, ‘x’], [‘b’, ‘y’], [‘c’, ‘x’], [‘c’, ‘y’]]
If you wish you can download the complete source code from cartesianProduct.groovy.