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
Brief explanation:
The
The
And then
And finally, to create the actual combinations, you will use
So, is there a more erlang way to do this?
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?