How to generate permutations from different sets of elements?

I’d like to generate a list from a variable length list of lists, choosing one element from each one. Like this:

list = [[:a, :b], [1, 2, 3], [{4, 5}, {5, 6}]]

magic_function(list)

Output:
[:a, 1, {4, 5}]
[:a, 1, {5, 6}]
[:a, 2, {4, 5}]
[:a, 2, {5, 6}]
[:a, 3, {4, 5}]
[:a, 3, {5, 6}]
[:b, 1, {4, 5}]
[:b, 1, {5, 6}]
[:b, 2, {4, 5}]
...

Is something like this possible in Elixir? I feel lost because of the variable length of the 2d list

1 Like

hello!

iex> [a, b, c] = [[:a, :b], [1, 2, 3], [{4, 5}, {5, 6}]]                            
iex> List.flatten(for e1 <- a, do: for e2 <- b, do: for e3 <- c, do: {e1, e2, e3})
[
  {:a, 1, {4, 5}},
  {:a, 1, {5, 6}},
  {:a, 2, {4, 5}},
  {:a, 2, {5, 6}},
  {:a, 3, {4, 5}},
  {:a, 3, {5, 6}},
  {:b, 1, {4, 5}},
  {:b, 1, {5, 6}},
  {:b, 2, {4, 5}},
  {:b, 2, {5, 6}},
  {:b, 3, {4, 5}},
  {:b, 3, {5, 6}}
]

is that close enough? :slight_smile:

2 Likes

This seems to be doing the trick:

Enum.reduce(list, fn acc, sublist ->
  for a <- sublist, b <- acc do
    List.flatten([a, b])
  end
end)

[
  [:a, 1, {4, 5}],
  [:a, 1, {5, 6}],
  [:a, 2, {4, 5}],
  [:a, 2, {5, 6}],
  [:a, 3, {4, 5}],
  [:a, 3, {5, 6}],
  [:b, 1, {4, 5}],
  [:b, 1, {5, 6}],
  [:b, 2, {4, 5}],
  [:b, 2, {5, 6}],
  [:b, 3, {4, 5}],
  [:b, 3, {5, 6}]
]

Unless the elements of some of the sublists are lists themselves, cause in that case they would be flattened.

UPDATE: This one below should cover all cases, just like @Eiji’s solution

def magic_function([]), do: []

def magic_function(list) do
  list
  |> Enum.reduce(fn sublist, acc ->
    for a <- acc, b <- sublist do
      [b | List.wrap(a)]
    end
  end)
  |> Enum.map(&Enum.reverse/1)
end
5 Likes

I believe this code is the best:

defmodule Example do
  # a function head declaring defaults
  def sample(list, data \\ [])

  # in case where empty list is passed as an input
  def sample([], []), do: []

  # data here is finished element of output list
  # due to prepending the data is reversed
  # which is fixed by `:lists.reverse/1`
  # we need to wrap the output element into one element list
  # otherwise our data is improperly concatenated
  # i.e. instead of list of lists we have just a list
  # for example: [:a, 1, {4, 5}, :a, 1, {5, 4}, :a, …]
  def sample([], data), do: [:lists.reverse(data)]

  # when heads i.e. elements of first list ends
  # all we need to do is to return an empty list
  # to make concatenation work
  def sample([[] | _tail], _data), do: []

  # collecting data and recursion part
  def sample([[sub_head | head] | tail], data) do
    # using ++ operator we concatenates two sides each returning a list of lists
    # left side returns an output result for first element (nested recursion)
    # right side returns an output result for rest elements (tail recursion)
    # collecting data is really simple
    # we are prepending a first element of head into data
    # until we reach end of nested levels
    sample(tail, [sub_head | data]) ++ sample([head | tail], data)
  end
end

Example.sample([[:a, :b], [1, 2, 3], [{4, 5}, {5, 6}]])

This code should be fastest and work as long as the input is list contains 1 or more lists.

The other solutions are limited to 3-element list and one of them have also other problem which was already mentioned by its author:

In my case all of below calls work:

# empty list
Example.sample([])
# one element list with no sub elements
Example.sample([[]])
# one element list
Example.sample([[:a, :b]])
# two element list
Example.sample([[:a, :b], [1, 2, 3]])
# three element list (author's example input)
Example.sample([[:a, :b], [1, 2, 3], [{4, 5}, {5, 6}]])
# three element list with lists as sub elements instead tuple
Example.sample([[:a, :b], [1, 2, 3], [[4, 5], [5, 6]]])
# four element list
Example.sample([[:a, :b], [1, 2, 3], [{4, 5}, {5, 6}], ["abc", "def"]])

Note: If one of root list is empty, for example:

[[:a, :b], [1, 2, 3], [], [{4, 5}, {5, 6}]]

then then my example would properly return empty list. If you want to simply skit empty elements use this code:

def sample([head | [[] | tail]], data), do: sample([head | tail], data)

right before “collecting data and recursion part” comment.

However the above does not work if empty list is a first element. To fix that you need an extra helper function to avoid conflicts in pattern-matching, for example:

defmodule Example do
  # if empty list is a first element
  def before_sample([[] | tail]), do: before_sample(tail)
  # in any other case
  def before_sample(list), do: list

  # definition of sample function goes here…
end

input = [[], [:a, :b], [1, 2, 3], [{4, 5}, {5, 6}]]

input
|> Example.before_sample()
|> Example.sample()
7 Likes

hands down :slight_smile:

I updated mine, should cover all cases now :crossed_fingers:

1 Like

Great you are improving answer, but no it does not works. If you want to enhance it then try all example cases I have shared in previous post.

Here is a result of one of them:

iex> Example.sample [[:a, :b]]
[[:a], [:b]]

iex> Example.magic_function [[:a, :b]]
** (Protocol.UndefinedError) protocol Enumerable not implemented for :a of type Atom
    (elixir 1.15.0-dev) lib/enum.ex:1: Enumerable.impl_for!/1
    (elixir 1.15.0-dev) lib/enum.ex:166: Enumerable.reduce/3
    (elixir 1.15.0-dev) lib/enum.ex:4307: Enum.reverse/1
    (elixir 1.15.0-dev) lib/enum.ex:1658: Enum."-map/2-lists^map/1-0-"/2
    iex:3: (file)

btw. I think it would be rather hard to write another solution which cover all cases, that I have shared, without recursion.

1 Like

Ah, good catch! Thanks.

I beg to differ. What about this one:

def magic_function([]), do: []

def magic_function(list) do
  list
  |> Enum.reduce([nil], fn sublist, acc ->
    for a <- acc, b <- sublist do
      [b | List.wrap(a)]
    end
  end)
  |> Enum.map(&Enum.reverse/1)
end

I think it covers all cases now. The initial accumulator of [nil] for the reduce handles the case when there’s only one sublist: the sublist’s elements are prepended to List.wrap(nil), which is an empty list.

So it appears recursion is not necessary after all

3 Likes

Not yet, you do not have an optional code for handling [] as element in root list. For now it correctly returns [] as output, but in my code you can optionally skip them. :smiling_imp:

Try calling:

iex> Example.magic_function([[:a, :b], [], [1, 2, 3]])
# correctly returns []
# bot does not allows to skip

Smart, I forgot about such List.wrap/1 behaviour. However I think it’s not really clear for eveyone what happens here …

Having in mind all cases and pattern-matching optimisations I would write it in this way:

defmodule Example do
  # uncomment if empty list is could be passed as an input
  # def sample([]), do: []

  # uncomment if empty list could be a first element
  # def sample([[] | tail]), do: sample(tail)

  # uncomment if list could contain only one element list
  # def sample([list]), do: Enum.map(list, &List.wrap/1)

  # in any other case

  # skip empty elements in root list
  def sample(list) do
    list |> Enum.reduce([], &sample/2) |> Enum.map(&Enum.reverse/1)
  end
  def sample([], data), do: data

  # alternatively do not skip empty elements in root list
  # def sample(list) do
  #   case Enum.reduce(list, [], &sample/2) do
  #     nil -> []
  #     list -> Enum.map(list, &Enum.reverse/1)
  #   end
  # end
  # when element is empty list, set data to nil
  # def sample([], _data), do: nil
  # no matter what happens later if data is nil keep it as is
  # def sample(_list, nil), do: nil

  # passing a first element of root list as data
  def sample(list, []), do: list

  def sample(list, data) do
    for sub_data <- data, element <- list do
      [element | List.wrap(sub_data)]
    end
  end
end

Of course there is no need to uncomment every part for example empty list as input would work, but would behave slightly slower without pattern-matching.

What’s more interesting are 2 code fragments to skip and not empty list inside root list. This is useful when Enum.filter/2 or similar is used to generate input.

1 Like

Thank you very much for this very educative discourse! I think this is an excellent way (for me at least) to learn. I will surely look through your previous posts for more Elixir fixes.

2 Likes

Thank you all for your replies, this turned into a very educational discourse. Hopefully this topic will be as useful for others as it was for me.

I had this question originally pop up during a school assignment (of which this function would be only a small but important part), in which we had to consider fast runtime and optimal code, so I’m especially thankful for @Eiji :blush:

1 Like

I wonder if there is any way to do this (passing Elji’s test cases) with a comprehension?

It’s easy when we know how many elements to combine.

[as, bs, cs] = [[:a, :b], [1, 2, 3], [{4, 5}, {5, 6}]]

for a <- as, b <- bs, c <- cs do
  {a, b, c}
end #=> [
  {:a, 1, {4, 5}},
  {:a, 1, {5, 6}},
  {:a, 2, {4, 5}},
  {:a, 2, {5, 6}},
  {:a, 3, {4, 5}},
  {:a, 3, {5, 6}},
  {:b, 1, {4, 5}},
  {:b, 1, {5, 6}},
  {:b, 2, {4, 5}},
  {:b, 2, {5, 6}},
  {:b, 3, {4, 5}},
  {:b, 3, {5, 6}}
]

But with an arbitrary list? @gregvaughn to the rescue! (because it’s your fault, that I’m always looking for the forsolution)

1 Like

Did you challenged a senior developer? :smiling_imp:

defmodule Example do
  def sample(list, opts \\ [skip: true])

  # uncomment if empty list is could be passed as an input
  def sample([], _opts), do: []

  # uncomment if empty list could be a first element
  def sample([[] | tail], opts), do: sample(tail, opts)

  # uncomment if list could contain only one element list
  def sample([list], _opts), do: Enum.map(list, &List.wrap/1)

  # in any other case
  def sample(list, opts) do
    if opts[:skip], do: sample_with_skip(list), else: sample_without_skip(list)
  end

  # skip empty elements in root list
  def sample_with_skip(list) do
    for sub_list <- list, reduce: [] do
      # skip empty elements in root list
      data when sub_list == [] ->
        data

      # passing a first element of root list as data
      [] ->
        sub_list

      data ->
        for sub_data <- data, element <- sub_list do
          [element | List.wrap(sub_data)]
        end
    end
    |> Enum.map(&Enum.reverse/1)
  end

  # alternatively do not skip empty elements in root list
  def sample_without_skip(list) do
    for sub_list <- list, reduce: [] do
      # when element is empty list set data to nil
      _data when sub_list == [] ->
        nil

      # no matter what happens later if data is nil keep it as is
      nil ->
        nil

      # passing a first element of root list as data
      [] ->
        sub_list

      data ->
        for sub_data <- data, element <- sub_list do
          [element | List.wrap(sub_data)]
        end
    end
    |> case do
      nil -> []
      list -> Enum.map(list, &Enum.reverse/1)
    end
  end
end

Pretty much the same as Enum.reduce/3 version. Simply pattern-matching here is not only in function clause, but also in for …, reduce: … clauseend notation.

However this looks like an art for art's sake. Just look how simple is raw pattern-matching comparing to 2 other versions of my solution. :smiley:

3 Likes

Oh, no! I suppose I’m building a reputation.

I was asked a variant of this at a job interview about 5 years ago and tried to make it work with a comprehension and failed. That was before the reduce option was added. I ultimately solved it with a recursive call to a comprehension. It needs a recursive/reduce style to handle the unknown count of lists.

However, now that I think about it, I wonder if a macro could generate the right count of generators in the for comprehension? Nah, only if the input is known at compile time.

1 Like