# 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
}
} 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]]
``````

## recent posts

• ### Open-Sourcing The Swift Talk Backend

Now written in Swift. π«

• ### Swift Tip: An NSScanner Alternative

Scanning without a Scanner

• ### Swift Talk for Teams

Share Swift Talk with your team with our improved team subscriptions.