Permutation for MutableCollection

permute.swift

import QuartzCore

/// Reorder elements in-place into the next permutation, returning false when
/// the collection has been permuted into lexicographical order. To cycle
/// through all permutations, start with a lexicographically-sorted collection
/// and permute until it returns false.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
public extension MutableCollection where Self: BidirectionalCollection {
    public mutating func permute(
        by areInIncreasingOrder: (Element,Element) throws ->Bool
    ) rethrows -> Bool {
        guard !isEmpty else { return false }
        var i = index(before: endIndex)
        
        while i != startIndex {
            let j = i
            formIndex(before: &i)
            let x = self[i]
            if try areInIncreasingOrder(x, self[j]) {
                guard let k = try lastIndex(where: { try areInIncreasingOrder(x, $0)})
                    else { preconditionFailure("Nodetermistic comparison behavior")}
                swapAt(i, k)
                self[j...].reverse()
                return true
            }
        }
        reverse()
        return false
    }
}

public extension MutableCollection where Self: BidirectionalCollection, Element: Comparable {
    mutating func permute() -> Bool {
        return self.permute(by: <)
    }
}

public struct Permutations<Elements: Collection> {
    internal let base: Elements
    internal let areInIncreasingOrder: (Elements.Element,Elements.Element)->Bool
    
    public init(_ base: Elements, by areInIncreasingOrder: @escaping (Elements.Element,Elements.Element)->Bool) {
        self.base = base
        self.areInIncreasingOrder = areInIncreasingOrder
    }
}

public extension Permutations where Elements.Element: Comparable {
    public init(_ base: Elements, by areInIncreasingOrder: @escaping (Elements.Element, Elements.Element)->Bool) {
        self.base = base
        self.areInIncreasingOrder = areInIncreasingOrder
    }
}

public extension Permutations {
    struct Index {
        var permutation: [Elements.Index]
        var position: Int?
    }
}

extension Permutations.Index: Equatable {
    public static func == (lhs: Permutations.Index, rhs: Permutations.Index) -> Bool {
        assert(lhs.position != rhs.position || lhs.permutation == rhs.permutation)
        return lhs.position == rhs.position
    }
}

extension Permutations.Index: Comparable {
    public static func < (lhs: Permutations.Index, rhs: Permutations.Index) -> Bool {
        switch (lhs.position,rhs.position) {
        case let (x?,y?): return x < y
        case (_?,nil): return true
        default: return false
        }
    }
}

extension Permutations: Collection {
    public func index(after i: Index) -> Index {
        var j = i
        formIndex(after: &j)
        return j
    }
    
    public func formIndex(after i: inout Index) {
        guard let n = i.position else { fatalError("Can't advance beyond endIndex") }
        if i.permutation.permute(by: { areInIncreasingOrder(base[$0],base[$1]) }) {
            i.position = n + 1
        } else {
            i.permutation = []
            i.position = nil
        }
    }
    
    public var startIndex: Index {
        return Index(permutation: Array(base.indices), position: 0)
    }
    
    public var endIndex: Index {
        return Index(permutation: [], position: nil)
    }
    
    public subscript(i: Index) -> LazyMapCollection<[Elements.Index],Elements.Element> {
        return i.permutation.lazy.map { self.base[$0] }
    }
}

public extension Collection {
    public func permutations(by areInIncreasingOrder: @escaping (Element,Element)->Bool) -> Permutations<Self> {
        return Permutations(self, by: areInIncreasingOrder)
    }
}

public extension Collection where Element: Comparable {
    public func permutations() -> Permutations<Self> {
        return Permutations(self, by: <)
    }
}

extension BidirectionalCollection where Self: MutableCollection {
    func permuted(
        by areInIncreasingOrder: (Element,Element)->Bool
    ) -> Self? {
        var new = self
        return new.permute(by: areInIncreasingOrder) ? new : nil
    }
}


var a = Array(1...8)
repeat {
    print(a)
} while a.permute(by: <)

let n = a.reduce(0,&+)


for _ in 0..<10 {
    let begin = CACurrentMediaTime()
    
    repeat {
        precondition(a.reduce(0,&+) == n)
    } while a.permute()
    
    let mid = CACurrentMediaTime()
    
    for p in a.permutations() {
        precondition(p.reduce(0,&+) == n)
    }
    
    
    let end = CACurrentMediaTime()
    
    print(Int(mid*1_000_000-begin*1_000_000),Int(end*1_000_000-mid*1_000_000))
}