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.
Very clever, I must say.
Excellnt logic, good work…thanks
I dont have any knowledge about List…How should I use this code..What should i use for …
import java.util.Arrays;
import java.util.List;
import java.util.ListIterator;
public class run{
public static void main(String args[])
{
Combinations combi=new Combinations(Arrays.asList( “How”, “Are”, “You”));
List n=combi.getCombinations();
ListIterator litr =n.listIterator();
while(litr.hasNext())
{
System.out.println(litr.next());
}
}
}
use this change to String
Change all “\” to \
Good work, but I have noticed it does not find all combinations, e.g. it does “foo bar”, but not “bar foo”.