Calculating Combinations in Erlang

One day, I tried to solve some problems on Project Euler that involve combination. I did it using erlang and produced a nice “by-product” in the form of erlang function that generates combinations of all elements in a list.

Here it is:

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:

Choosing one item from [a b c] gives us choices of [a] [b] or [c]. So for 1-combination:
combos(1, [a,b,c]) = [[a],[b],[c]]

combos(1, L) -> [[X] || X <-L];

Next, choosing 3 items from [a b c] gives us only one choice: [abc]. So, for K-combination where K equals length of the list:
combos(3, [a,b,c]) = [[a,b,c]]

combos(K, L) when K == length(L) -> [L];

Now, choosing 3 items from [a b c d e] gives us these choices:
a and two more from [b c d e], plus
b and two more from [c d e], plus
c and two more from [d e].
combos(3, [a,b,c,d,e]) =
[a,b,d],
[a,b,e],
[a,c,d],
[a,c,e],
[a,d,e],
[b,c,d],
[b,c,e],
[b,d,e],
[c,d,e]]

combos(K, [H|T]) ->
    [[H | Subcombos] || Subcombos <- combos(K-1, T)]
    ++(combos(K, T)).

Finally, to get all combinations, simply do 1-combination through (list’s length)-combination:

combos(L) ->
    lists:foldl(
        fun(K, Acc) -> Acc++(combos(K, L)) end,
        [[]],
        lists:seq(1, length(L))
    ).

which gives final output:

combos([a,b,c,d]) =
[[],
 [a],
 [b],
 [c],
 [d],
 [a,b],
 [a,c],
 [a,d],
 [b,c],
 [b,d],
 [c,d],
 [a,b,c],
 [a,b,d],
 [a,c,d],
 [b,c,d],
 [a,b,c,d]]

 

I use empty list as starting accumulator for the reduce step because empty list is a valid combination (to choose none is a choice).

PS: Seth Ladd’s implementation here seems to perform faster especially on long list.

Advertisements

2 thoughts on “Calculating Combinations in Erlang

  1. Interesting post – I also needed this function and had mine (almost) working when I found your post.

    I suspect that using ++ is what costs you when the lists get longer.

    My effort was as follows:

    % --- special cases
    combs([], _N)	->	[];
    combs(List, N)	when N  length(List)
    				->	[];
    % --- normal case
    combs(List, N)	->	lists:reverse(combs(List, N, [], [])).
    
    combs(List,  0, Comb, Acc)	->	[lists:reverse(Comb)|Acc];
    combs([],    _, _,    Acc)	->	Acc;
    combs([H|T], N, Comb, Acc)	->
    	NewAcc = combs(T, N-1, [H|Comb], Acc),
    	combs(T, N, Comb, NewAcc).
    

    This performs much faster and will handle larger parameters before it crashes the VM.

    I did not compare this against the Seth Ladd function you provided a link to, but this is MUCH simpler.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s