Seth Ladd's Blog

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)); ...

Well, thanks to the many people ( here and here ) that provided their versions of an erlang way to calculate combinations , I've really begun to open my mind to how to think functionally. To help me understand what is going on, I've converted the basic idea into a Ruby version of calculation combinations. This uses recursion like the erlang versions do. class Array def head_tail [self.first, self.tail] end def tail self[1,self.size-1] end end def combos(list) return [[]] if list.empty? h, t = list.head_tail t_combos = combos(t) t_combos.inject([]) {|memo, obj| memo << [h] + obj} + t_combos end c = combos([1,2,3,4]) require 'pp' pp c As you can see, I added a bit of erlangism to the Array class, by adding a method to get the head and tail of an array. Let's run through this. On the first call to combos([1,2,3,4]) we jump over the first line (the exit in our recursion). We generate the head and tail, which in this case is 1 and [2,3...

I recently had to calculate all possible combinations of a set. I needed to calculate combinations of 1..N size, where N is the size of the original set of things. Order inside of the resulting combinations did not matter to me, as I am treating the combinations as true sets. For example, given the set [A,B,C] , I needed to calculate the following combinations: [] [A] [B] [C] [AB] [AC] [BC] [ABC] It dawned on me that a cool way to generate the combinations was to treat the sets (the original set and the resulting combination sets) as bit strings. If the bit corresponding to the member is on, I include the member in the combination. To explain, I start with the set [A,B,C] . I create a number that has three bits, all on, one for each member of the set. I therefore have the binary number 111 matching [A,B,C] . 111 happens to be 7 in decimal, which is one less than the total number of combinations I require. Starting with zero, I loop up and including seven (for a total of eight i...