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.


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];

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