How can I iterate over all permutations in a list of unknown dimensions

Questions / Help
1

Hi I need a bit of help…

I’ve read various answers to questions regarding getting all of the permutations of a list, but that’s not my problem. I have a list of list like this…

[[1, 2, 3], [4, 5], [6, 7], [1]]

What I want is a function to create list of all permutations of each of item in each list, so feeding the above list into this function would return…

[
  [1, 4, 6, 1],
  [1, 4, 7, 1],
  [1, 5, 6, 1],
  [1, 5, 7, 1],
  [2, 4, 6, 1],
  [2, 4, 7, 1],
  [2, 5, 6, 1],
  [2, 5, 7, 1],
  [3, 4, 6, 1],
  [3, 4, 7, 1],
  [3, 5, 6, 1],
  [3, 5, 7, 1]
]

I could use a nested comprehension if I knew there were only 4 dimensions. The thing is, I don’t know how many dimensions this list of lists is going to have.

2

Well, I managed to create a solution that works, but with all those list concatenations, it is super ineficient.

defmodule Combinations do
  def combinations(list) do
    combos([], hd(list), tl(list), [])   
  end
  
  defp combos(first, on, next, acc) do
    Enum.reduce(on, acc, fn n, acc ->
      if next == [] do
        [first ++ [n] | acc]
      else
        combos(first ++ [n], hd(next), tl(next), acc)
      end
    end
    )
  end
end

lists = [[1, 2, 3], [4, 5], [6, 7], [1]]
Combinations.combinations(lists)

outputs

[
  [3, 5, 7, 1],
  [3, 5, 6, 1],
  [3, 4, 7, 1],
  [3, 4, 6, 1],
  [2, 5, 7, 1],
  [2, 5, 6, 1],
  [2, 4, 7, 1],
  [2, 4, 6, 1],
  [1, 5, 7, 1],
  [1, 5, 6, 1],
  [1, 4, 7, 1],
  [1, 4, 6, 1]
]
3

The core of this solution is noticing that adding an additional list to the input means taking every existing permutation and adding each element of the new list.

defmodule Foo do
  def permutations(list) do
    Enum.reduce(list, fn els, acc ->
      Stream.flat_map(els, fn el ->
        Stream.map(acc, fn perm ->
          [el | List.wrap(perm)]
        end)
      end)
    end)
  end
end

iex(12)> Foo.permutations(d) |> Enum.to_list()
[
  [1, 6, 4, 1],
  [1, 6, 4, 2],
  [1, 6, 4, 3],
  [1, 6, 5, 1],
  [1, 6, 5, 2],
  [1, 6, 5, 3],
  [1, 7, 4, 1],
  [1, 7, 4, 2],
  [1, 7, 4, 3],
  [1, 7, 5, 1],
  [1, 7, 5, 2],
  [1, 7, 5, 3]
]

These come out with each element in the reverse order, but if that bothers you consider reversing the input to Foo.permutation.

5 Likes
4

Thanks! That solution is indeed much more elegant and faster than mine. For my uses, I changed the Stream versions of flat_map and map to the Enum versions and it was even faster.

Although I appreciate that using a Stream will help if the number of permutations gets large, which it very easily can.

5

A different way to think about this is to think of each permutation as being a list of indexes into each of those inner lists. For example:

input = [[1, 2], [3, 4]]

Here, the indexes for each permutation/generation are:

permuation list 1 index list 2 index
1 0 0
2 0 1
3 1 0
4 1 1

If we imagined those indexes as the list of lists:

steps = [
  [0,0],
  [0,1],
  [1,0],
  [1,1],
]

Here you can see for the first list [1,2] we “stay” on index 0 for 2 permutations before ticking over to index 1 for two generations. For the second list [3,4] we “stay” on a given index for 1 tick only.

We could apply these indexes to the inputs like so:

Enum.reduce(steps, [], fn indexes, acc -> 
  permutation = Enum.zip_with(input, indexes, &Enum.at(&1, &2))
  [permutation | acc]
end)
|> Enum.reverse()

Yielding us:

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

So the question becomes, is there a way to generate the correct list of indexes we’d need for each step, for each list? Well, there is a pattern at play. The general rule is for each list we “stay” on a specific index for N generations, where N is the length of the list after it multiplied by the length of the list after that and so on (ie the cartesian product).

To see this, let’s look at your original example:

[[1, 2, 3], [4, 5], [6, 7], [1]]

in the first list [1,2,3] we stay at index 0 for 4 steps / permutations. Why 4? Because length([4,5]) * length([6,7]) * length([1]) == 4. If we were to write our the indexes for this list for every permutation it would look like this:

000011112222

to generate this we use the formula current_permutation mod total_permutations / how long we stay on an index.

We know there are only 3 items in the first list so their are only 3 indexes, meaning total number of permutations is 3*4 = 12.

The formula for this then is:

index_for_permutation = div(
  rem(permutation_number, repetitions), 
  steps_on_an_index
)

Since we know there are 12 permutations total for input, and that we stay on an index for 4, we get:

index_for_permutation = div(
  rem(permutation_number, 12), 
  4
)

So we can:

for n <- 0..(12 - 1) do
    index = div(rem(n, 12), 4)
end

Now to generalise to all lists it’s easier to start at the end and work back:

    reversed = input |> Enum.reverse()
    [rightmost_list | rest_lists] = reversed

    index_info =
      rest_lists
      |> Enum.reduce([{length(rightmost_list), 1}], fn list, [{total_prior_steps, _} | _] = acc ->
        total_steps = length(list) * total_prior_steps
        [{total_steps, total_prior_steps} | acc]
      end)

generates:

[{12, 4}, {4, 2}, {2, 1}, {1, 1}]

which are the two numbers for each list that we need to plug into our formula.
Now we can generalise the above:

defmodule Combinations do
  def combinations(input) do
    reversed = input |> Enum.reverse()
    [rightmost_list | rest_lists] = reversed

    index_info =
      rest_lists
      |> Enum.reduce([{length(rightmost_list), 1}], fn list, [{total_prior_steps, _} | _] = acc ->
        total_steps = length(list) * total_prior_steps
        [{total_steps, total_prior_steps} | acc]
      end)

    [{total_number_of_permutations, _} | _] = index_info

    for n <- 0..(total_number_of_permutations - 1) do
      Enum.zip_with(input, index_info, fn list, {repetitions, steps_on_an_index} ->
        index = div(rem(n, repetitions), steps_on_an_index)
        Enum.at(list, index)
      end)
    end
  end
end

lists = [[1, 2, 3], [4, 5], [6, 7], [1]]
Combinations.combinations(lists)

I’m not sure if this is faster or anything given lists are linked lists in Elixir and such, but it was fun to come up with.

6

In general, Enum.at is performance Kryptonite in a loop - it adds a slowdown factor of O(N) to everything because it has to traverse the list every call. If you need to random-access data, it’s best to pick a different data structure like tuples (constant time) or maps (O(log N) time).

You can also use streams to make the cycle representation more explicit:

defmodule Foo do
  def permutations(list) do
    total_results =
      list
      |> Enum.map(&length/1)
      |> Enum.product()

    list
    |> Enum.map(&Stream.cycle/1)
    |> Stream.zip()
    |> Stream.take(total_results)
  end
end

This returns each permutation as a tuple instead of a list, but close enough

1 Like
7

TIL about Enum.product, I even looked for that :see_no_evil:

I don’t think streams have much to do with it they’ll often make performance worse. But yea like I said lists being linked lists makes my approach bad, if we had actual arrays I suspect it would perform better.

You can of course transform the input first:

defmodule Combinations do
  def permutations(input) do
    input = input |> Enum.map(&List.to_tuple/1)

    {_, index_info} =
      input
      |> Enum.reverse()
      |> Enum.reduce({1, []}, fn list, {total_prior_steps, acc} ->
        total_steps = tuple_size(list) * total_prior_steps
        {total_steps, [{total_steps, total_prior_steps} | acc]}
      end)

    [{total_number_of_permutations, _} | _] = index_info

    for n <- 0..(total_number_of_permutations - 1) do
      Enum.zip_with(input, index_info, fn list, {repetitions, steps_on_an_index} ->
        elem(list, div(rem(n, repetitions), steps_on_an_index))
      end)
    end
  end

  def input(x, y) do
    for a <- 0..x do
      for b <- 0..y do
        a + b
      end
    end
  end
end

Combinations.input(3, 5) |> Combinations.permutations

would be interesting to benchmark.

8

I believe Joe’s original version in Erlang is:

perms([]) -> [[]];
perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].

which appeared in his thesis, his ProgErl book, and probably many erlang-questions posts. Sorry, I don’t have references to hand right now.

It’s easy to understand:

  • the head of the result varies over all the input list
  • the tail of the result is all permutations of the remaining input

Translate to Elixir and warp for your nested List Of Lists problem (LOL).

Try this direct translation of Joe’s code:

  def perms([]), do: [[]]
  def perms([hs|ts]) do
    for h <- hs, t <- perms(ts), do: [h|t]
  end

BTW, looks like a graph isomorphism problem - I’m working on the same thing at the moment :slight_smile:

2 Likes