# Functional Snippet #10: Permutations

In this snippet we’ll look at how to generate all permutations of the elements of an array. First we need to define the auxiliary function `between`

. It computes all possible ways to insert an element `x`

into an array `ys`

. We could use a for-loop to accomplish this, but here we’ll use `map`

, `decompose`

and recursion instead:

```
func between<T>(x: T, ys: [T]) -> [[T]] {
if let (head, tail) = ys.decompose {
return [[x] + ys] + between(x, tail).map { [head] + $0 }
} else {
return [[x]]
}
}
```

If `ys`

is an empty array, there’s only one way to insert `x`

and therefore the return value is `[[x]]`

. When `ys`

is non-empty, we can either insert `x`

as the very first element (`[[x] + ys]`

) or somewhere in the tail of the array. To accomplish the latter, we make the recursive call `between(x, tail)`

and reconstruct the original array by adding `head`

to the front of all these possible insertions.

```
between(0, [1, 2, 3])
> [[0, 1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3], [1, 2, 3, 0]]
```

To define the `permutations`

function we use the same pattern: decomposing the array and recursing on the tail.

```
func permutations<T>(xs: [T]) -> [[T]] {
if let (head, tail) = xs.decompose {
return permutations(tail) >>= { permTail in
between(head, permTail)
}
} else {
return [[]]
}
}
```

If `xs`

is empty, there’s only one permutation: `[[]]`

. If `xs`

is non-empty, we first calculate all possible permutations of the tail of `xs`

. For each of these permutations, we calculate the different ways to insert the first element of the original array, `head`

, into the permuted tail by calling `between(head, permTail)`

. We could use `map`

to do so, but this would return a value of type `[[[T]]]`

rather than `[[T]]`

. Therefore we use the flatmap operator (`>>=`

) on arrays defined in a previous snippet to combine the results.

```
permutations([1, 2, 3])
> [[1, 2, 3], [2, 1, 3], [2, 3, 1],
[1, 3, 2], [3, 1, 2], [3, 2, 1]]
```