I’ve been hacking away at my ongoing Chord project, and I ran into a situation where I needed to generate all possible permutations of length k for a given list of elements, where repetitions of elements from our list are allowed. I figured this would be an excellent opportunity to flex our Elixir muscles and dive into a few possible solutions.

Base Cases

Let’s get the ball rolling by defining a Permutation module to hold our solution and a with_repetitions/2 function that accepts a list of elements, and a value for k:

defmodule Permutation do
  def with_repetitions(list, k)
end

We’ll start by defining a few base cases for our with_repetitions/2 function. First, if list is empty, we’ll want to return a list who’s first element is an empty list:

def with_repetitions([], _k), do: [[]]

We’ll do the same if k is 0:

def with_repetitions(_list, 0), do: [[]]

Note that we’re returning [[]] because the only possible permutations of an empty list, and the only possible zero-length permutation of a list is []. The list of all possible permutations, in that case, is [[]].

Building Our Permutator

Now we come to the interesting case where both list and k have workable values:

def with_repetitions(list, k) do
  # ...
end

We’ll start by mapping over every element in our list. We’ll use each of these elements as the head of a new k-length permutation we’re building.

list
|> Enum.map(fn head ->
  # ...
end)

For each value of head, we want to calculate all n - 1 length sub-permutations of our list, and concatenate each of these sub-permutations to our head:

list
|> with_repetitions(k - 1)
|> Enum.map(fn tail ->
  [head] ++ tail
end)

At this point, the result of our with_repetitions/2 function is a list of a list of permutations. For every head, we’re returning a list of all k-length permutations starting with that head. What we really want is a singly nested list of all permutations we’ve found.

I find myself producing lots of ranging content from books and articles, like the one you're reading now, to open source software projects. If you like what I'm doing, nothing shows your support more than signing up for my mailing list.

To reduce our list of lists of permutations, we need to append each list of permutations for every value of head together:

|> Enum.reduce(&(&2 ++ &1))

This will order our permutations in lexical order (assuming our initial list was sorted). If we wanted our final set of permutations in reverse order, we could switch the order of our concatenation:

|> Enum.reduce(&(&1 ++ &2))

Or we could just use Kernel.++/2 to accomplish the same thing:

|> Enum.reduce(&Kernel.++/2)

Simplifying with Special Forms

This pattern of nested mapping and consolidating our result into a flat list of results is a fairly common pattern that we run into when writing functional code. It’s so common, in fact, that Elixir includes a special form specifically designed to make this kind of computation easier to handle.

Behold the list comprehension:

def with_repetitions(list, k) do
  for head <- list, tail <- with_repetitions(list, k - 1), do: [head | tail]
end

This single line is functionally equivalent to our original with_repetitions/2 function. The for tells us that we’re starting a list comprehension. For every value of head and every value of tail, we build a new permutation ([head | tail]). The result of our list comprehension is simply a list of all of these permutations.

Without Repetition

We’ve been trying to find permutations where repetitions of elements from list are allowed. How would we solve a similar problem where repetitions aren’t allowed?

It turns out that the solution is fairly straight-forward. When we generate our set of sub-permutations, or tail values, we can simply pass in list without the current value of head:

def without_repetitions(list, k) do
  for head <- list, tail <- without_repetitions(list -- [head], k - 1), 
    do: [head | tail]
end

That’s it! Each level of our permutation removes the current value of head preventing it from being re-used in future sub-permutations. It’s fantastically convenient that previously computed values in our list comprehension, like head, can be used in the subsequent values we iterate over.