Wednesday, August 1, 2007

Calculating Combinations the Erlang Way

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?

2 comments:

Semergence » Blog Archive » Calculating Combinations Using Java and Lots of Bits said...

[...] 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 an efficient way to do it without resorting [...]

Ron said...

How about this?

combos(1, L) -> [[X] || X <-L];
combos(K, L) when K == length(L) -> [L];
combos(K, [H|T]) ->
[[H | Subcombos] || Subcombos <- combos(K-1, T)]
++(combos(K, T)).

combos(L) ->
lists:foldl(
fun(K, Acc) -> Acc++(combos(K, L)) end,
[[]],
lists:seq(1, length(L))
).

(explanation here)

I guess your version is faster, though.