# Generate all combinations having a fixed array size

Hi, I’m trying to solve a problem where I want to generate all possible combinations from an array, with at most n elements. I was looking at this thread today: Most elegant way to generate all permutations? where this really nice solution was proposed by @OvermindDL1:

``````def permutations([]), do: [[]]
def permutations(list), do: for elem <- list, rest <- permutations(list--[elem]), do: [elem|rest]
``````

So, I was trying to adapt this code to generate combinations with a fixed number of elements.
Example: Given the array `[1, 2, 3, 4]` and a maximum size of 2, all possible combinations¹ would be:

``````[1, 2],
[1, 3],
[1, 4],
[2, 1],
[2, 3],
[2, 4],
[3, 1],
[3, 2],
[3, 4],
[4, 1],
[4, 2],
[4, 3],
``````

¹Just to be clear that: all possible combinations, in this case, means: combining every element with 2 more from the array until all elements have been combined.

PS.: I’m not completely comfortable with Elixir yet. So, forgive me if this is something too obvious to be asking here .

3 Likes
``````iex(2)> for x <- [1,2,3,4], y <- [1,2,3,4], x != y, do: [x, y]
[
[1, 2],
[1, 3],
[1, 4],
[2, 1],
[2, 3],
[2, 4],
[3, 1],
[3, 2],
[3, 4],
[4, 1],
[4, 2],
[4, 3]
]
``````
4 Likes

List comprehensions offer a cartesian product of elements, but you want to exclude pairs of the same value, which can be achieved with a filter in the comprehension

``````iex> elements = 1..4
iex> for x <- elements, y <- elements, x != y, do: [x, y]
[
[1, 2],
[1, 3],
[1, 4],
[2, 1],
[2, 3],
[2, 4],
[3, 1],
[3, 2],
[3, 4],
[4, 1],
[4, 2],
[4, 3]
]
``````

edit: haha, sniped by @preciz

4 Likes

`h for`

Thanks a lot for the kind responses @preciz and @gregvaughn.
I’ve been reading the docs again, and I completely missed the part about filters (Was kinda lost about all the option combinations you can pass to `for`, to be honest).

One thing that remains though, is that the max size of the resulting array is variable, so instead of 2, it could be 3 or 4, for instance. So, how would I, do this combination instead of manually typing the generators?

That’s where you want recursion like your original code. I once did a job interview question where I needed to figure out the combinations of N 6 sided dice

``````defp combinations(dice) do
combinations(dice - 1, (for x <- 1..6, do: [x]))
end

defp combinations(0, acc), do: acc

defp combinations(remaining_dice, acc) do
combinations(remaining_dice - 1, (for x <- 1..6, y <- acc, do: [x | y]))
end
``````
3 Likes

I’ve found this solution on the web that does exactly what I need. Even though I’m still trying to wrap my head around on how this works as it works (I guess it gets easier to apply these concepts along the way!?)

``````defp combinations(0, _), do: [[]]
defp combinations(_, []), do: []
defp combinations(size, [head | tail]) do
(for elem <- combinations(size-1, tail), do: [head|elem]) ++ combinations(size, tail)
end
``````

Another thing that is getting me curious about the first code is why changing the return type breaks the result. I mean, when the list is over (already pattern-matched), why does it matter returning `[[]]` over `[]`?

``````# Calling: Permute.permutations [1,2,3]
# Returns: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
defmodule Permute do
def permutations([]), do: [[]] # <-- (!)
def permutations(list), do: for elem <- list, rest <- permutations(list--[elem]), do: [elem|rest]
end
``````

``````# Calling: Permute.permutations [1,2,3]
# Returns: []
defmodule Permute do
def permutations([]), do: [] # <-- (!)
def permutations(list), do: for elem <- list, rest <- permutations(list--[elem]), do: [elem|rest]
end
``````

Update: Whild guess: Maybe it breaks because `for` needs something to iterate over when `permutations(list--[elem])` reduces the list?

1 Like

Because it is expecting a list for further permutations, and the outer list just wraps the comprehension, thus it is a comprehension (the outer `[]`) returning an empty list (`[]`) conceptually.

Essentially yes. Though to be specific it keeps the lists as proper lists.

1 Like

You might check the implementation generating both lists and streams for both combinations and permutations in my package `Formulae`.

It’s OSS, so welcome to examine the source.

The implementation is fully based on macros; basically it generates the nested `for` clauses for lists and nested `Stream.transform` clauses for the input.

3 Likes

Essentially dealing with `list` not with `Stream` when doing permutations is a dead end

Huh?

Try permutations by, say, 10 from the alphabet (26 items )

Obviously, but if I had to do that it would not only eat all memory but also all ‘time’ as well, so I’d have bigger issues, especially as a stream would make that take exponentially longer too!

Yes and no. With a stream it’s possible to get the result in a reasonable time if one needs e.g. all the permutations containing only one `"a"`.

With the package I mentioned above, the following code returns instantly:

``````(for c <- ?a..?z, do: <<c>>)
|> Formulae.Combinators.Stream.permutations(10)
|> elem(0)
|> Stream.filter(fn a -> Enum.count(a, & &1 == "a") == 1 end)
|> Enum.take(100)
``````

It might process all the permutations with `Stream.run/1` in a reasonable amount of time as well.

Then it’s not getting all permutations then, you could easily make a far more optimized version that still doesn’t use streams and will run in a fraction of the time of the streams version.

Hello,

I want to check if a given list of items has a combination of 3 elements matching a predicate. The predicate will give the same result for `a, b, c` and `b, c, a` for example, so there is no need to check both.

The list of items can contain less than 3 items though.

I had an implementation for advent of code that I copied from internet (probably from this forum):

``````defp combinations(_list, 0), do: [[]]
defp combinations([], _num), do: []

defp combinations([head | tail], num) do
Enum.map(combinations(tail, num - 1), &[head | &1]) ++
combinations(tail, num)
end
``````

And I would use it like that: (I just want a boolean in the end)

``````combinations(list, 3)
|> Enum.any?(fn
[a, b, c] when Deck.is_set?(a, b, c) -> true
_ -> false
end)
``````

I tried to make a more optimized solution and had good results according to Benchee.

``````# comb/1
defp comb([]), do: false
defp comb([_, _ | []]), do: false
defp comb([a | tail]), do: comb(tail, a) || comb(tail)
# comb/2
def comb([b | tail], a), do: comb(tail, a, b) || comb(tail, a)
def comb([], _), do: false
# comb/3
def comb([c | tail], a, b) when Deck.is_set?(a, b, c), do: true
def comb([_ | tail], a, b), do: comb(tail, a, b)
def comb([], _, _), do: false
``````

And I just call it `comb(list) :: bool`.

Now I am not sure that the function is correct. It seems to. But is there any better way of doing it ?

Thank you

Edit: this is for implementing Set, a game. The guard `is_set?` checks that for 3 items (an item is a 4-tuple), elements in the same tuple position are the same for the 3 items, or are all different.

I refactored this a bit:

``````def cartesian_product([ head | tail ]) do

tail
|> Enum.reduce(head, fn xs, acc -> for x <- xs, y <- acc, do: [x | y] end)
|> Enum.map(&Enum.reverse/1)
end
``````

Just because I usually prefer `Enum.reduce/3` over plain recursion, no other reason.

I reworked it to allow giving a list of enumerables instead (something I was looking for):

iex(1)> Test.cartesian_product([1…2, 3…4, 5…6])
[
[1, 3, 5],
[2, 3, 5],
[1, 4, 5],
[2, 4, 5],
[1, 3, 6],
[2, 3, 6],
[1, 4, 6],
[2, 4, 6]
]

1 Like

Just had a need for your library and I am stopping by to tell you that I love it. Thanks for making it!

1 Like