Generate all combinations having a fixed array size

Questions / Help
1

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 :sweat_smile:.

3 Likes
2 
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]
]
5 Likes
3

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

5 Likes
4

@thiagomajesk if you want to learn more about this just type in iex:
h for

5

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?

6

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
4 Likes
7

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
8

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. :slight_smile:

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

1 Like
9

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
10

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

11

Huh? 

12

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

13

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! :wink:

14

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.

15

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.

16

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.

17

I refactored this a bit:

def cartesian_product([ head | tail ]) do
    head = Enum.map(head, &List.wrap/1)

    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. :slightly_smiling_face:

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
18

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