I took time off from implementing a UInt72
type to bang out versions of C++'s permutation functions.
To detect permutations:
extension Collection {
func isPermutation<C: Collection>(of other: C, by areEquivalent: (Element, Element) throws -> Bool) rethrows -> Bool where C.Element == Element {
var myIndices = Array(indices), otherIndices = Array(other.indices)
while let nextIndex = myIndices.first {
guard myIndices.count == otherIndices.count else { return false }
let nextValue = self[nextIndex]
let pivot = try myIndices.partition { try areEquivalent(self[$0], nextValue) }
let otherPivot = try otherIndices.partition { try areEquivalent(other[$0], nextValue) }
let myMatchCount = myIndices.distance(from: pivot, to: myIndices.endIndex)
let otherMatchCount = otherIndices.distance(from: otherPivot, to: otherIndices.endIndex)
guard myMatchCount == otherMatchCount else { return false }
myIndices.removeLast(myMatchCount)
otherIndices.removeLast(otherMatchCount)
}
return otherIndices.isEmpty
}
}
extension Collection where Element: Equatable {
func isPermutation<C: Collection>(of other: C) -> Bool where C.Element == Element {
return isPermutation(of: other, by: ==)
}
}
I tried doing it like the example at C++ Reference did (and hence the initial request for std::mismatch
), but here I started over. Instead of something like mismatch
, I used the existing partition
method to segregate each unique value from the rest. It took me a while to think on how to do the loop since I only have equality tests, neither less-than or hashes to compare elements.
Even if we add an implementation like this, my diverges
and converges
methods should still be added.
Can anyone please figure out the time/space/comparison complexity of my implementation? The sample from C++ Reference uses O(n) if mismatch
short-circuits the tests and O(n^2) otherwise.
Then I looked at the implementation of std::next_permutation
at C++ Reference, and was trying to figure out what that code was doing. I got insight by reading a page by Mark Nelson from a web search.
I started out with direct adaptation:
guard !isEmpty else { return false }
var i = index(before: endIndex)
guard startIndex != i else { return false }
then wondered if I can compact the loop code and not need these early tests. Yes, I could. And I can use on-point methods instead of implying what's going on with loops, and using better names for the iteration variables helped:
@discardableResult
mutating func permuteForward() -> Bool {
let backIndices = indices.reversed()
for current in backIndices {
guard let previous = index(current, offsetBy: -1, limitedBy: startIndex) else { break }
guard self[previous] < self[current] else { continue } // Change to comparison closure.
let switchOut = backIndices[backIndices.index(where: { self[previous] < self[$0] })!]
swapAt(previous, switchOut)
self[current ..< endIndex].reverse()
return true
}
reverse()
return false
}
The empty- and one-element guards were dropped with the loop ending at the first pass or the first calculation of previous
, and with useless no-op calls to reverse()
. I looked at the implementation of std::prev_permutation
at C++ Reference and its differences with the forward version, then adapted it too.
extension BidirectionalCollection where Self: MutableCollection {
@discardableResult
mutating func permuteForward(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool {
let backIndices = indices.reversed()
for current in backIndices.dropLast() {
let previous = index(before: current)
guard try areInIncreasingOrder(self[previous], self[current]) else { continue }
let lastNotLessThanPrevious = try backIndices[backIndices.index(where: { try areInIncreasingOrder(self[previous], self[$0]) })!]
swapAt(previous, lastNotLessThanPrevious)
self[current ..< endIndex].reverse()
return true
}
reverse()
return false
}
@discardableResult
mutating func permuteBackward(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool {
let backIndices = indices.reversed()
for current in backIndices.dropLast() {
let previous = index(before: current)
guard try areInIncreasingOrder(self[current], self[previous]) else { continue }
let lastLessThanPrevious = try backIndices[backIndices.index(where: { try areInIncreasingOrder(self[$0], self[previous]) })!]
swapAt(previous, lastLessThanPrevious)
self[current ..< endIndex].reverse()
return true
}
reverse()
return false
}
}
extension Collection {
func nextPermutation(orderedBy areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element]? {
var result = Array(self)
let hasMore = try result.permuteForward(by: areInIncreasingOrder)
return hasMore ? result : nil
}
func previousPermutation(orderedBy areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element]? {
var result = Array(self)
let hasMore = try result.permuteBackward(by: areInIncreasingOrder)
return hasMore ? result : nil
}
}
extension Collection where Element: Comparable {
func nextPermutation() -> [Element]? {
return nextPermutation(orderedBy: <)
}
func previousPermutation() -> [Element]? {
return previousPermutation(orderedBy: <)
}
}
extension RangeReplaceableCollection {
func nextPermutation(orderedBy areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Self? {
let result: [Element]? = try self.nextPermutation(orderedBy: areInIncreasingOrder)
return result.map { Self($0) }
}
func previousPermutation(orderedBy areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Self? {
let result: [Element]? = try self.previousPermutation(orderedBy: areInIncreasingOrder)
return result.map { Self($0) }
}
}
extension RangeReplaceableCollection where Element: Comparable {
func nextPermutation() -> Self? {
return nextPermutation(orderedBy: <)
}
func previousPermutation() -> Self? {
return previousPermutation(orderedBy: <)
}
}
Hopefully, I've kept the same time/space/comparison complexity.