Java code to generate word combinations

Say, you have a list of words like “foo bar moo”. You want to generate all combinations of this list.

foo
bar
moo
foo bar
bar moo
foo moo
foo bar moo

Below is the piece of java code to do this. I got this idea from one of the threads in perl monks.

public class Combinations<T> {
  private List<T> originalList;

  public Combinations(List<T> originalList) {
	this.originalList = originalList;
  }

  public List<List<T>> getCombinations() {
	List<List<T>> combinations = new LinkedList<List<T>>();
	
	int size = this.originalList.size();
	
	int threshold = Double.valueOf(Math.pow(2, size)).intValue() - 1; 
	
	for (int i = 1; i <= threshold; ++i) {
	  LinkedList<T> individualCombinationList = new LinkedList<T>();
	  int count = size - 1;
	  
	  int clonedI = i;
	  while (count >= 0) {
		if ((clonedI & 1) != 0) {
		  individualCombinationList.addFirst(this.originalList.get(count));
		}
		
		clonedI = clonedI >>> 1;
		--count;
	  }
	  
	  combinations.add(individualCombinationList);

	}
	
	return combinations;
  }
}

Basic idea here is to map your combinations to binary digits. For the above list it would be

000 ->empty list
001 ->moo
010->bar
011->bar, moo
100->foo
101->foo,moo
110->foo,bar
111->foo,bar,moo

So, all you have to do is

1. Iterate from 1 to 2 ^ list size – 1.
2. Right shift each of the formed digits and if the right most digit is one pick the object from the appropriate position in the list.

Advertisements

Code, Java, Programming

June 9, 2009

6 Comments