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?
Hey Seth… cool to see you’re working on learning erlang too. I bought the Armstrong book and have been picking away at it. So far I’m liking it.
I’m pretty green so I don’t really know if there’s a more erlang way to do this. Well, I imagine that most erlangers would write some cascade of recursive functions passing an accumulator.
But I put a few minutes into it and it looks like it would be pretty complex. Also what I started to come up with was getting all the orderings too (”ba” as well as “ab”)… doesn’t look like you want that.
Actually, I have to say that the bit map approach is pretty ingenious… take care.
Ben Munat
2 Aug 07 at 9:45 pm
It’s been a few years since I last wrote Erlang, so I can’t say if this is idiomatic or not. But it’s certainly shorter:
powerset([]) ->
[[]];
powerset([X|XS]) ->
lists:concat(lists:map(fun(S) -> [S,[X|S]] end, powerset(XS))).
As usual, the Haskell implementation is even nicer:
powerset = filterM (const [True, False])
Juha Komulainen
3 Aug 07 at 12:02 am
It seems like there is a more mathematical (perhaps functional) way to do it.
In pseudocode:
combos( [] ) -> [ [] ].
combos( [H|T] ) ->
CT = combos( T ),
append( CT, map( fun(HS) -> [H | HS], CT ) ).
In other words, first find the combinations of the “rest” of the list. That’s exactly half of the combinations. The other half of the combinations is each of those, combined with the first element of the list. This should actually produce the elements in the same order that your original method does.
masonium
3 Aug 07 at 8:28 am
I don’t know if this is more erlangy, but to generate the mask, I would use a list comprehension like this:
mask(0) ->
[[]];
mask(N) when N > 0 ->
[ [X | Y] || X <- [true, false], Y <- mask(N - 1) ].
Then to calculate the combinations:
comb(List) ->
% Create a list masks for each combination
Masks = mask(length(List)),
I have commented each line to explain, and I also have included a commented version of each line which does not use list comprehensions, which may be clearer.
Finally, my golf score on this is 103:
c(L)->[[X||{X,_}<-E]||E<-[lists:filter(fun({_,M})->M end,C)||C<-[lists:zip(L,M)||M<-mask(length(L))]]].David Mercer
3 Aug 07 at 8:35 am
Ben: I haven’t been too happy with the Programming Erlang book to be honest. I can’t complain too much, as there aren’t many options, but his writing style sounds very preachy. Plus, he keeps referring to things he hasn’t mentioned yet. It’s annoying to see elements of the language that he hasn’t covered yet. Some reorganization would be very helpful.
sethladd
3 Aug 07 at 8:49 am
I sat there and looked at that filter, sure that there was a shorter way to do it, but couldn’t figure it out. Soon after I posted, I read http://weblog.hypotheticalabs.com/?p=137, which explained that list comprehensions can be used for filtering, too. Using those techniques, I have my golf score down to 66:
c(L)->[[V||{V,true}<-C]||C<-[lists:zip(L,M)||M<-mask(length(L))]].
Of course, this still relies on my definition of mask/1, which I’m not counting against me. Masonium’s post above, though, gives me some ideas.
David Mercer
3 Aug 07 at 8:54 am
combos([]) ->
[[]];
combos([H|T]) ->
lists:append([[[H|L],L] || L <- combos(T)]).
Jason
3 Aug 07 at 9:00 am
OK, thanks to Masonium’s comment, I have now managed to golf this problem down to 45 characters, and I don’t even need the mask/1 function I defined earlier but then didn’t count against my score. Here is the all-in-one combination generator function:
David Mercer
3 Aug 07 at 9:05 am
David, looking good! I’ve read that using ++ like that is bad form. Of course, as an erlang n00b, what do I know?
sethladd
3 Aug 07 at 9:11 am
Jason, I bow down to you, sir.
sethladd
3 Aug 07 at 9:15 am
This one’s a higher golf score (50), but much more efficient, since it only calls itself once. Thanks to Jason’s comment above for the idea.
David Mercer
3 Aug 07 at 9:17 am
[...] thanks to the many people (here and here) that provided their versions of an erlang way to calculate combinations, I’ve [...]
Semergence » Blog Archive » Calculating Combinations In Ruby From Erlang
4 Aug 07 at 9:53 pm
Wow, I didn’t think it was possible to get it that (@Jason/David) compact. In my aborted attempt, I was trying the “local function with accumulator” approach. I need to work on my list comprehension mojo… seems very powerful indeed.
One question though: is the solution here tail recursive? If I’m understanding it right, I don’t think it is… process() is called recursively with the tail, and then as these calls exit, the results are used by the list comprehension and passed to append.
To test my theory out, I figured I’d see how it does with a bit longer list…. like, uh, a hundred or so elements. The answer is “don’t do that”… it makes your computer very very unhappy.
So, anyone have another version — even if it’s not quite so compact — that isn’t a potential DOS?
Ben Munat
5 Aug 07 at 10:23 am
I might be wrong here, but I think listing the combinations of any more than, say, 20 elements is unreasonable. There are 1,048,576 combinations of 20 elements. Your example of 100 elements would produce a list of length 1,267,650,600,228,229,401,496,703,205,376 elements (each element being itself a list of 0–100 elements). I don’t know the statistics on the amount of memory in the world (or the number of electrons in the universe), but I am guessing that is much larger than any memory in the universe can hold.
For that reason, worrying whether the function is tail-recursive is probably not important, since you’re not going to have that many levels of recursion. If you do manage to procure enough memory to run the calculation, the stack space taken up by the recursion is insignificant next to the memory requirements of your result.
David Mercer
6 Aug 07 at 5:20 am
[...] 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 [...]
Semergence » Blog Archive » Calculating Combinations Using Java and Lots of Bits
21 Oct 08 at 4:32 pm