Unlimited Cartesian Product in Java - part 2

(This is the second part, see part 1).

Here is the code that implements Cartesian product in Java. The implementation amounts to providing the following methods of class Cartesian:

 
    public static <X, XS extends Iterable<X>>
        Iterable<Iterable<X>> product(final XS... xss) {
      return product(Arrays.asList(xss));
    }

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

So we could write code like this:

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

and like this:

  Iterable<Iterable<Integer>> theProduct = 
    Cartesian.product(
        Arrays.asList(1, 2, 3), 
        Arrays.asList(4, 5, 6));

Note that we could not use Iterable<Iterable<X>>, since, imagine, in this case we could not even build a product of Set<Set<X>>.

How do we calculateProduct? The idea is that we define it by recursion. If we have X0, X1,..., Xn, we define product(X0, X1,..., Xn) as X0 x product(X1, X1,..., Xn); and if the sequence is actually empty, we return a singleton,

new ArrayList<Iterable>() {{
            add(Collections.EMPTY_LIST);
          }};

(I use crazybob's contraption to build the singleton).

  private Iterable<Iterable<X>>
      calculateProduct(final Iterable<XS> xss) {
    if (xss.iterator().hasNext()) {
      Pair<XS, Iterable<XS>> pair = split(xss);
      XS head = pair.x();
      Iterable<XS> tail = pair.y();
      return appendComponentToProduct(head, calculateProduct(tail));
    } else {
      return new ArrayList<Iterable<X>>() {{
        add(Collections.EMPTY_LIST);
      }};
    }
  }

Here I use two methods, split and appendComponentToProduct. The first one is obvious (okay, it's an exercise if you are a beginner); the second one is here. See what it does: we have a component, X0, say,

[1, 2, 3]

, and a product of previous components X1 x ... x Xn, which is an iterable of iterables, e.g. [[4, 5], [5, 6]]; we need to append elements of X0 to all elements of the partial product. That appendage function is called consWith: it takes an x and appends it to all partial product elements. We apply this function to the whole X0; what we receive has to be flattened to produce a list of tuples [x0, x1, ..., xn]

  private Iterable<Iterable<X>>
      appendComponentToProduct(
        XS component, 
        Iterable<Iterable<X>> partialProduct) {
      // E.g. [1, 2, 3], [[4, 6], [5, 6]] -> 
      // [[[1, 4, 6], [1, 5, 6]], [[2, 4, 6], [2, 5, 6]], [[3, 4, 6], [3, 5, 6]]] ->
      // [[1, 4, 6], [1, 5, 6], [2, 4, 6], [2, 5, 6], [3, 4, 6], [3, 5, 6]] 
      return flatten(consWith(partialProduct).map(component));

Flattening is, again, a trivial exercise; let's take a look at our consWith. It is a method that returns a function (which we apply to the component X0:

    public <ElementOfProduct extends Iterable<X>>
        Function<X, Iterable<Iterable<X>>>
        consWith(final Iterable<ElementOfProduct> pxs) {
      return new Function<X, Iterable<Iterable<X>>>() {
        // takes an x, returns a function appending x to sequences
        public Iterable<Iterable<X>> apply(final X x) {
          // Takes a sequence [x1, x2, ...], returns [x, x1, x2, ...]
          return new Function<ElementOfProduct, Iterable<X>>() {
            public Iterable<X> apply(ElementOfProduct y) {
              return concat(Arrays.asList(x), y);
            }
          }.map(pxs);
        }
      };
    }

A little bit dizzy? It's okay. We have arrived to the summit.

This is Higher Order Java!