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.