Calculating Combinations Using Java and Lots of Bits

I was feeling nostalgic and went back to see how I calculated combinations in Erlang and combinations in Ruby. I wanted to see if there was a fun way to do it without resorting to recursion.

I started with my crazy hack to use bit strings to calculate combinations. I didn't want to resort to creating bit strings, as I wanted to minimize the amount of work I needed to do. Therefore, I thought about simply using bitwise operators.

Below is my Java algorithm for creating calculations using iteration and bitwise operators to create all combinations from an array.

Thoughts?


public static void generate(String[] list) {
int max = (int) Math.pow(list.length, 2)-1;
System.out.println(max + " combinations");
for (long i = 0; i < max; i++) {
String[] combo = new String[Long.bitCount(i)];
int comboPos = 0;
for (int j = 0; j < list.length; j++) {
if ((i & (1L< 0) {
combo[comboPos++] = list[j];
}
}
//System.out.println(Arrays.toString(combo));
}
}


Update: handle up to 64 slots. Will need to move to something like BigInteger to handle greater than 64 bits I suppose. Wonder how that will affect performance?
1 comment

Popular posts from this blog