Iterating Multi-Dimension Permutations
Why don't you subscribe to my blog while you're here? I'm a freelance web developer and I blog about Ruby, Rails, and business online.
Go ahead and subscribe to my RSS feed. Thanks for visiting!
Ever needed to iterate a multi-dimensional array? This is an easy problem if you know the size of each dimension, otherwise it’s a real bitch. For example, this is easy: “Iterate all permutations of A where A is a set {X, Y, Z}, and X: {1, 2, 3}, Y: {4, 5, 6}, Z: {7, 8, 9}”, but this is hard: “Iterate all permutations of A where A is a set {X, Y, Z}, and X: {1, 2, 3, …, n1}, Y: {4, 5, 6, …, n2}, Z: {7, 8, 9, …, n3}”. That’s only two dimensions too, imagine going to more - youch! These problems come up most often in scientific applications, but you also find derivatives in resource allocation, scheduling, and probably other places I can’t think of right now. Below is some Java code (complete with unit tests!) that I wrote for a recent project that will allow you to iterate all permutations of a multi-dimensional collection of unknown size.
Here’s the source. The unit tests are first so you can see what this thing is mean to do. Note that this source can theoretically work with more than two dimensions, but I only needed two so that’s all I’ve tested for.
/*
* ChainTest.java
* JUnit based test
*
* Created on February 6, 2007, 6:36 AM
*/
package phabian.util;
import junit.framework.*;
import java.util.Collection;
import java.util.Iterator;
import java.util.ArrayList;
/**
*
* @author alex
*/
public class ChainTest extends TestCase {
ArrayList<Collection> iterable = new ArrayList<Collection>();
public ChainTest(String testName) {
super(testName);
}
protected void setUp() throws Exception {
ArrayList<String> alpha = new ArrayList<String>();
alpha.add("a");
alpha.add("b");
alpha.add("c");
alpha.add("d");
ArrayList<String> alpha2 = new ArrayList<String>();
alpha2.add("x");
alpha2.add("y");
alpha2.add("z");
ArrayList<Integer> num = new ArrayList<Integer>();
num.add(1);
num.add(2);
num.add(3);
ArrayList<Integer> num2 = new ArrayList<Integer>();
num2.add(7);
num2.add(8);
num2.add(9);
iterable.add(alpha);
iterable.add(num);
iterable.add(alpha2);
iterable.add(num2);
}
protected void tearDown() throws Exception {
}
/**
* Test of getValue method, of class phabian.util.Chain.
*/
public void testGetValue() {
Chain instance = new Chain(iterable, null);
instance.next();
instance.next();
instance.next();
instance.next();
Collection value = instance.getValue();
Collection<Object> expResult = new ArrayList<Object>();
expResult.add("a");
expResult.add(1);
expResult.add("y");
expResult.add(7);
Collection result = instance.getValue();
assertEquals(expResult, result);
}
/**
* Test of hasNext method, of class phabian.util.Chain.
*/
public void testHasNext() {
Chain instance = new Chain(iterable, null);
int combinations = 0;
while (instance.hasNext()) {
instance.next();
combinations++;
}
assertEquals(108, combinations);
}
/**
* Test of next method, of class phabian.util.Chain.
*/
public void testNext() {
Chain instance = new Chain(iterable, null);
// Go next a few times.
instance.next();
instance.next();
instance.next();
Collection value = instance.next();
// Check value returned is correct.
Collection<Object> expResult = new ArrayList<Object>();
expResult.add("a");
expResult.add(1);
expResult.add("y");
expResult.add(7);
Collection result = instance.getValue();
assertEquals(expResult, result);
// Go next one more time.
instance.next();
value = instance.getValue();
expResult = new ArrayList<Object>();
expResult.add("a");
expResult.add(1);
expResult.add("y");
expResult.add(8);
result = instance.getValue();
assertEquals(expResult, result);
}
}
Here’s the source. I had to remove the class comment because it was messing with the syntax highlighter, so here it is below instead of in the code…
/*
* Chain.java
*
* Created on February 5, 2007, 8:06 PM
* The basic idea is to create a Chain from a Collection.
* Each Chain has a left and right, in the same way a doubly linked list has.
* Next() on the parent Chain passes the Next() call down to the leaf Chain.
* When a Chain overflows (hasNext() == false) then an overflow event is called
* on the parent of the overflowing Chain and the parent Chain increments to
* compensate for the overflow. This increment can also create an overflow.
* The iteration of the Chain (and it's siblings) is complete when all Chains
* return hasNext() == false.
*
*/
package phabian.util;
import java.util.Collection;
import java.util.Iterator;
import java.util.ArrayList;
/**
*
* @author alex
*/
public class Chain implements Iterator {
/** An iterator for Chain's that house other chains.
* This prevents Chain from iterating over subordinates chains.
*/
private class ContainerIterator implements Iterator {
public boolean hasNext() {
return false;
}
public Object next() {
return new Object();
}
public void remove() {
throw new UnsupportedOperationException();
}
}
private Collection collection;
private Iterator iterator;
private Chain left;
private Chain right;
// This Chain contains other chains, so it's classed as a container.
// The value of a container is the current value of each collection contained.
private boolean container = false;
// The current value of the iterator.
private Object value;
public Chain(Collection collection, Chain left) {
this.collection = collection;
// Only iterate over this collection if we are not housing further collections.
if (!collection.isEmpty() &&
!(collection.toArray()[0] instanceof Collection) ) {
this.iterator = collection.iterator();
} else {
this.iterator = new ContainerIterator();
}
this.left = left;
if (left != null) {
left.link(this);
}
left = this;
for (Object o : collection) {
if (o instanceof Collection) {
Chain previous = new Chain((Collection)o, left);
left = previous;
}
}
}
public void link(Chain right) {
this.right = right;
}
public Collection<Object> getValue() {
ArrayList<Object> value = new ArrayList<Object>();
if ( ! (this.iterator instanceof ContainerIterator)) {
value.add(this.value);
}
if (right != null) {
value.addAll(right.getValue());
}
return value;
}
public Iterator iterator() {
return this;
}
/** Our subordinate chain overflowed, so we need to increment too.
*/
public void overflowEvent(Chain right) {
next(false);
}
public boolean hasNext() {
boolean hasNext = iterator.hasNext();
if (right != null) {
hasNext = hasNext || right.hasNext();
}
return hasNext;
}
public Collection next() {
return next(true);
}
/** Increment the subordinate chain, or ourselves if we were directed
* to not pass it on.
*/
private Collection next(boolean passItOn) {
passItOn = passItOn && (right != null);
if (passItOn) {
// Initialize our value to make it look like we did something.
if (this.value == null) {
this.value = iterator.next();
}
// Pass it on.
right.next(true);
} else {
if ( ! iterator.hasNext()) {
if (this.left != null) {
this.left.overflowEvent(this);
}
iterator = collection.iterator();
}
this.value = iterator.next();
}
return getValue();
}
public void remove() {
throw new UnsupportedOperationException();
}
}
You can think of the code as a business. On his way to golf, the CEO commands the CTO to do stuff. Before the CTO leaves to join the CEO for a round of golf, the CTO instructs mid-level management to get stuff done. mid-level management have lots of coffee to drink so they instruct their project manager to get stuff done. The project manager is too busy day trading to do anything else, so he tells his team leader to get stuff done. The team leader is swamped with other work so he tells his overly enthusiastic team leader wanna-be to get stuff done.
After some time, the wanna-be team leader gets it done, and tells the team leader, who tells his project manager, who tells mid-level management, who in turns notifies the CTO via mobile phone, who tells the CEO over a beer at the 19th hole.
And that, is how life the code above works.
