Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Permutation for MutableCollection
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))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.