Generate Permutations of a Swift Array

Array+Permutations.swift

// abey.dev

import Foundation

extension Array {
    func decompose() -> (Iterator.Element, [Iterator.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: x, tail).map { [head] + $0 }
}

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

// Example
let permutations = permutations(for: [1, 2, 3])
// permutations = [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]