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

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),
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.