The problem: Write an algorithm that can provide combinations of a given word. The combinations need not contain a new word with the same letters.
Input: ABCDE
OUTPUT: ABCDE, ABCD, BCDE, ABC, BCD, CDE, AB, BC, CD, DE etc.
There are several algorithms out there that describe how to create effective combinations, SEPA does permutations, bubble sort and nested loops etc.
After spending some time looking for what’s been done - the one I liked the most was as follows: [0,0,0], [0,0,1], [0,1,1] [1,1,1]: null, A, AB ABC etc.
Incrementing decimals, start with zero, get a binary representation and map it to the array positions. This will give the combinations in constant time. A very efficient algorithm.
/**
* Take a word and return a collection of combinations
* @param sortedWord
* @return
*/
public Collection<String> generateCombinations(String sortedWord)
{
Collection<String> c=new HashSet<String>();
char[] broken=sortedWord.toCharArray();
int combinationLength=new Double(Math.pow(2L, (new Long(sortedWord.length())).longValue())).intValue();
// System.out.println("Combination len="+combinationLength);
for(int loop=combinationLength-1;loop>0;loop--)
{
String binary=fillWithZeros(Long.toBinaryString(loop),sortedWord.length());
char[] bins=binary.toCharArray();
StringBuffer wb=new StringBuffer();
for(int a=0;a<bins.length;a++)
{
Integer binValue=new Integer(""+bins[a]);
if(binValue.intValue()==1)
{
wb.append(broken[a]);
}
}
c.add(wb.toString());
}
While there is a nested loop, the loops can be replaced with other techniques.
This is a very high performance combination creation technique. Comments/Improvements are welcome.
