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

If you recall, I wrote some Ruby code to calculate combinations of values in lists. I needed to create a list of all combinations of values, where each combination had between 0 and N number of values, where N is equal to length of the source list. (I’m not sure I’m explaining that correctly, but refer to my previous post for examples).

Here’s my first shot at how to do this in erlang. It look longer to find math:pow and how to convert a float to an integer in erlang than to write the actual code.

-module(s).
-export([combos/1]).

combos(L) -> combos(L, bit_masks(length(L))).

combos(L, [BH|BT]) ->
  [mask_list(L, BH)|combos(L, BT)];
combos(_, []) -> [].

mask_list([H|T], [BH|BT]) ->
  case (BH) of
    1 -> [H|mask_list(T, BT)] ;
    0 -> mask_list(T, BT)
  end;
mask_list([], []) -> [].

bit_masks(NumColumns) ->
  bit_masks(0, round(math:pow(2, NumColumns))-1, NumColumns).

bit_masks(Max, Max, NumColumns) ->
  [padl(NumColumns, bl(Max))];

bit_masks(X, Max, NumColumns) ->
  [padl(NumColumns, bl(X)) | bit_masks(X+1, Max, NumColumns)].

padl(N, L) when N =:= length(L) -> L ;
padl(N, L) when N > length(L) -> padl(N, [0|L]).

bl(N) -> bl(N, []).

bl(0, Accum) -> Accum;
bl(N, Accum) -> bl(N bsr 1, [(N band 1) | Accum]).

Brief explanation:

The bl function creates a “bit list”, given a number and an accumulator. So, bl(5,[]) will return [1,0,1].

The padl function pads the list, which is useful when you want to ensure that all combinations ultimately have the same length. So, padl(4, [0]) would return [0,0,0,0].

And then bit_masks creates a list of bit masks which we’ll use to create the combinations. For example, bit_masks(4) returns:

[[1,1,1,1],
 [1,1,1,0],
 [1,1,0,1],
 [1,1,0,0],
 [1,0,1,1],
 [1,0,1,0],
 [1,0,0,1],
 [1,0,0,0],
 [0,1,1,1],
 [0,1,1,0],
 [0,1,0,1],
 [0,1,0,0],
 [0,0,1,1],
 [0,0,1,0],
 [0,0,0,1],
 [0,0,0,0]]

And finally, to create the actual combinations, you will use combos. Example: combos([a,b,c,d]). This generates a result of:

[[],
 [d],
 [c],
 [c,d],
 [b],
 [b,d],
 [b,c],
 [b,c,d],
 [a],
 [a,d],
 [a,c],
 [a,c,d],
 [a,b],
 [a,b,d],
 [a,b,c],
 [a,b,c,d]]

So, is there a more erlang way to do this?