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 2.0 (Xcode 7.0)

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

Thx for this, works great!

Swift 3 needs little bit of tweaking to work.

Thanks so much for this! FWIW, I've updated the code to Swift 5, and made a few stylistic changes for personal preference.

What's the Big O of this? LogN?

Updated this to Swift 5.2 🙌

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>(xs: [T]) -> [[T]] {
    guard let (head, tail) = xs.decompose() else { return [[]] }
    return permutations(xs: tail).flatMap { between(x: head, $0) }
}

Updated this to Swift 5.2 🙌

Great, thank you!