Unlimited Cartesian Product in Java - part 1

You probably know what Cartesian product is. Take two sets, A and B, their product, A x B, is a set of all pairs (a, b), where a belongs to A and b belongs to B. Something like that.

Here I am going to show how to build a Cartesian product for an unlimited collection of sets, or rather for an Iterable of Iterables. Unlimited means any number starting from 0. Due to limitations of Java, all these component sets (or rather component Iterables, will have the same element type.

More formally, given a sequence of sets (or of sequences), A0, A1, ... An, we will produce A = A0 x A1 x ... x An, whose elements are sequences (a0, a1, ..., an), where each ai belongs to Ai.

So, for instance if we have just A0 and A1, their product will be the following: {(a0, a1}.

With this definition, we, with some confusion, have to admit that the Cartesian product of just one A0 is a set of singletons, {(a)} for all a in A. Of course there is a canonical one-to-one correspondence between A and its "product".

More curious is the question what exactly is the product of 0 of components. In a category with limits it is a terminal object, 1. But how about JVM? There's no such thing as a terminal object.

No problem. We can use our definition, and take the set of empty sequences. There's just one empty sequence, so our canonical singleton has the following form:
{{}}. Did you notice the underlying type is not even mentioned. We have an Iterable of one single empty iterable of what type? Actually, Java deduces it from the type of the variable the product is assigned to. That's the safest way to pass the type knowledge into the executing code.

So, the solution I propose is to have something like this:

    Iterable<Iterable<Integer>> actual = Cartesian.product(Arrays.asList(Arrays.asList(1, 2, 3), Arrays.asList(4, 5, 6)));
    assertEquals(9, Set(actual).size());

Note the funny function name: Cartesian.product. Why do we need the special class named Cartesian? For two reasons. One, it is a neat way to provide type parameterization; second, calculating the product is not an elementary operation, so we need a bunch of private methods to help us. In JavaScript this can be accomplished by defining functions within our function; in Haskell we could comfortably add to our main definition the auxiliary "where" definitions. In Java, the "where" become class or instance methods.

So, we are introducing a special class named Cartesian, with just one exposed method, product:

  public static class Cartesian<X, XS extends Iterable<X>> {
  ...
    public static <X, XS extends Iterable<X>> Iterable<Iterable<X>> product(final Iterable<XS> xss) {
      return new Cartesian<X, XS>().calculateProduct(xss);
    }
    ...

You've noticed the IT parameter type. The reason for having this parameter is that we can pass for product calculations all kinds of Iterables of Iterables: Sets of Lists, Lists of Sets... any combination would work.

First, the algorithm. Here's how lj user=_navi_ defines it:

    product :: [[a]] -> [[a]]
    product [] = [[]]
    product (xs:xss) = product' xs (product xss)
      where
        product' xs pxs = concat $ map (\x -> map (x:) pxs) xs

In plain words, for us, Java pdestrians, it means this:

Say, we have an Iterable consisting of the first component, and the tail. And suppose we already have a product (call it pxs) built for the tail.
Then we do the following: scan the first component, A0 attaching its elements ai to the head of each element of the already built product.

We do this by having a function (let's call it f(a0, as) that concatenates an element a0 with the tail [a1, ..., an], producing a new sequence [a0, ..., an].
Having function f, we build another function, g(a) that builds a list of all [a0, ..., an] - by mapping the product of the tail, pxs using the function f: g returns, for each a0, a list of concatenations built by f.

So, for each element a the function g produces a list. Now let's apply this to all the elements of the first component, A0: that is, transform the component... to what? To a sequence of sequences of sequences.

We do not need such a deep structure. We just need the sequences of the lower level, listed in some order or in no order. So we do what is known as flattening the list.

The important thing is that the product we build should be lazy. As an example, suppose we build all permutations of N elements. This is equivalent to building a cartesian product of [0..N-1] x [0..N-2] x ... x [0..1] x [0]; there's N! elements in the product. We do not want to fill our whole memory with these elements before we start processing them.


(the code is published and commented in the second part)