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?
0 comments:
Post a Comment