Introduction
I recently ran into a problem while building the type compiler for my proprietary scripting language. It seemed like a braindead problem I should have remembered from my high-school days of coding. After reviewing a few recursive and somewhat clumsy examples on the Internet, and also after decidedly turning down Guava (In interest of compactness, external dependencies on my compiler are kept at a minimum), I decided to attack the problem on my own.
Problem
Calculate the complete list of n-tuple combinations of elements in a set of arbitrary type. For example, computing the triple (3-tuple) list of combinations of the following set should satisfy the following:
Input: [1, 2, 3, 4, 5]
Output: [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]
Features
I came up with a solution that boasts the following features:- Iterable (no memory consumption)
- Non-recursive (no stack juggling)
- n-tuple combinations only (as opposed to permutations)
Code
Here's the code:
package com.extollit.collect;
import java.text.MessageFormat;
import java.util.*;
public class CombinationsIterable<T> implements Iterable<List<T>> {
private final List<T> delegate;
private final int rank;
/**
* Create an iterable list over the specified list that returns an iterator for iterating over
* all the n-tuple combinations in the list (n-tuple specified by the rank parameter).
*
* @param delegate The list to compute n-tuple sub-set combinations from
* @param rank The size of the combination tuple, must be > 0 and <= delegate size
*/
public CombinationsIterable(List<T> delegate, int rank) {
this.delegate = delegate;
if (rank > delegate.size() || rank <= 0)
throw new IllegalArgumentException(
MessageFormat.format("Combination tuple size (rank) must be less than or equal to the delegate list size and greater than zero, but {0} <= 0 | > {1}", rank, delegate.size())
);
this.rank = rank;
}
@Override
public Iterator<List<T>> iterator() {
return new ComboIter();
}
private class ComboIter implements Iterator<List<T>> {
private final ArrayList<T> workspace = new ArrayList<T>(rank);
private final int [] indexStack;
private final int spanSize;
private int stackPointer;
private List<T> current = null;
private ComboIter() {
indexStack = new int[rank];
stackPointer = 0;
indexStack[0] = -1;
spanSize = delegate.size() - indexStack.length;
for (int c = 0; c < indexStack.length; ++c)
workspace.add(c, null);
}
private List<T> findNext() {
while (stackPointer >= 0 && ++indexStack[stackPointer] > spanSize + stackPointer) {
stackPointer--;
}
if (stackPointer >= 0) {
this.workspace.set(stackPointer, delegate.get(indexStack[stackPointer]));
for (int c = stackPointer + 1; c < indexStack.length; ++c) {
indexStack[c] = indexStack[c - 1] + 1;
++stackPointer;
this.workspace.set(c, delegate.get(indexStack[c]));
}
return this.workspace;
} else
return null;
}
@Override
public boolean hasNext() {
return acquireCurrent() != null;
}
@Override
public List<T> next() {
List<T> current = acquireCurrent();
if (current != null) {
current = new ArrayList<T>(current);
this.current = findNext();
}
return current;
}
private List<T> acquireCurrent() {
if (this.current == null)
this.current = findNext();
return this.current;
}
@Override
public void remove() {
throw new UnsupportedOperationException(
"Combinations iterator does not support removal of combinations because it's functional mapping to the underlying collection is non-injective"
);
}
}
}
It passes a few of my tests, please notify me of any errors.