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]]