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:
[...] 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 [...]
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.
Post a Comment