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

Popular posts from this blog

Converting Array to List in Scala

I ported a JavaScript app to Dart. Here's what I learned.

Minification is not enough, you need tree shaking