*(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 `X`_{0}, X_{1},..., X_{n}

, we define `product(X`_{0}, X_{1},..., X_{n})

as `X`_{0} x product(X_{1}, X_{1},..., X_{n})

; 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, `X`_{0}

, say, [1, 2, 3], and a product of previous components

`X`_{1} x ... x X_{n}

, which is an iterable of iterables, e.g. [[4, 5], [5, 6]]; we need to append elements of `X`_{0}

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 `X`_{0}

; 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 `X`_{0}

:

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!*

## 3 comments:

Figuring out and completing this code may have taught me more Java than an entire semester of formal instruction. :)

For other solutions, see Stack Overflow.

Post a Comment