Generate Combinations

While writing programs we frequently want to get all combinations of a set. It su@%s to code it every time we want it. Won’t it be good to a have a Class ‘CombinationGenerator’? And do operations like this:

CombinationGenerator cg = new CombinationGenerator(collection, 3);
/* where collection is something that implements ‘Collection’ and k – size of each combination */
while(cg.hasNext) {
process(cg.next());
}

This exactly is what the following class does:

import java.util.Collection;
import java.util.Iterator;
import java.util.Vector;

public class CombinationGenerator implements Iterator{

	Vector<Object> 	list 		= new Vector<Object>();
	Collection 		collection;
	Vector<Object> 	curComb;
	Vector<Integer> nextComb;
	int 			N, R;
	boolean 		hasNext;

	public CombinationGenerator(Collection argCollection, int argR) {
		this.collection = argCollection;
		this.R 			= argR;
		this.N 			= this.collection.size();
		this.hasNext 	= true;

		if(argCollection.size()<argR) throw new IllegalArgumentException();

		curComb 	= new Vector<Object>();
		nextComb 	= new Vector<Integer>();

		for(int i=0; i<R; i++)
			nextComb.add(i);

		for(Object obj : collection)
			list.add(obj);
	}

	public Object next() {
		fillComb();

		int i;
		int l = nextComb.size();

		for(i = l-1; i>=0; i--) {
			int el = nextComb.elementAt(i);
			if( el!=N-1 && ( i==l-1 || el+1!=nextComb.elementAt(i+1) ) ) {
				nextComb.set(i, el+1);
				break;
			}
		}

		if(i==-1) {
			hasNext=false;
		} else {
			for(int j=i+1; j<l; j++) {
				nextComb.set(j, nextComb.elementAt(j-1)+1);
			}
		}

		return curComb;
	}

	public boolean hasNext() {
		return this.hasNext;
	}

	private void fillComb() {
		curComb = new Vector<Object>();
		for(int i: nextComb) {
			curComb.add(list.elementAt(i));
		}
	}

	public void remove() {
		throw new UnsupportedOperationException();
	}
}

Here is a quick example on how to use it:

Vector<Integer> vect = new Vector<Integer> ();
for(int i=1; i<=3; i++) {
    vect.add(i);
}

CombinationGenerator cg = new CombinationGenerator(vect, 2);

while(cg.hasNext) {
    System.out.println(cg.next());
}

Output:

[1, 2]
[1, 3]
[2, 3]

:-)