When I find something interesting and new, I post it here - that's mostly programming, of course, not everything.

Monday, October 06, 2008

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!

3 comments:

Matthew Flaschen said...
This comment has been removed by the author.
Matthew Flaschen said...

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

jmkristian said...

For other solutions, see Stack Overflow.

Followers

Subscribe To My Podcast

whos.amung.us