# 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?

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
# 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
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

I updated mine, should cover all cases now

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.

``````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.

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

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 `for`solution)

1 Like

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.

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