How to generate permutations from different sets of elements?

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.

Did you challenged a senior developer?

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.

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)

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

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.

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.

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.

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

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.

hands down

I updated mine, should cover all cases now

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()