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.

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(&(&2 ++ &1))
```

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