Generate the permutations of a Swift array.

Permutations.swift

//: Permutations
//  based on https://www.objc.io/blog/2014/12/08/functional-snippet-10-permutations/
//  but updated for Swift 3.0 (Xcode 8.3)

extension Array {
  func decompose() -> (Generator.Element, [Generator.Element])? {
    guard let x = first else { return nil }
    return (x, Array(self[1..<count]))
  }
}

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

let example = between(0, [1, 2, 3])
// example = [[0, 1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3], [1, 2, 3, 0]]


func permutations<T>(_ xs: [T]) -> [[T]] {
  guard let (head, tail) = xs.decompose() else { return [[]] }
  return permutations(tail).flatMap { between(head, $0) }
}

let p = permutations([1, 2, 3])
// p = [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]