Semergence

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,4] respectively. We immediately begin our recursion by saying, “Get me all the combinations for the tail, which is essentially everything but the head.” Then, for each of those combinations, we append the head (again, here it’s 1). Finally, we add all of the rest of the combinations and return the array of arrays.

Another way to explain it might be:

1. H = Remove an element from the list.
2. T = The rest of the list.
3. C = Calculate the combinations of T (recursion happens here).
4. C2 = For each combination in C, generate a new combination by appending H.
5. return C2 + C

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 iterations, once for each combo that I want). I convert each iteration count to a binary string, which will give me which bits are on for this combination.

For example, here’s the ruby code:

original_set = [:A, :B, :C]
combinations = []

def create_combo(bit_string, original_set)
  combo = []
  bit_string.split(//).each_with_index do |bit, i|
    combo << original_set[i] if bit == "1"
  end
  combo
end

(2**original_set.size).times do |i|
  bit_string = sprintf("%03b", i)
  combinations << create_combo(bit_string, original_set)
end

require 'pp'
pp combinations

This will print out:

[[], [:C], [:B], [:B, :C], [:A], [:A, :C], [:A, :B], [:A, :B, :C]]

Neat, huh?

I’m sure you can speed this up by checking each bit in the iteration count instead of first converting to a bit string.