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.