Blasts from the past: algorithms

Looking at my browser tabs, I noticed I had one on C++'s std::prev_permutation function. I was probably thinking of proposing to add it to Swift’s Standard Library. Then I just wondered if I was repeating myself. Sure enough, I found some algorithms that fell by the Swift 3 wayside. Since more kinds of changes are allowed for 4.x and 5, and we just added conditional conformance, maybe we can reconsider them:

Any other ones I’m missing?

The decision rationale states that rotate was deferred because:

If it does re-arise, then I am going to get a head start on bikeshedding and suggest the spellings “rotate(startingAt: Index)” and “rotated(startingAt: Index)”.

The names have already been extensively bikeshedded and rotate(shiftingToStart:) was considered the most clear. To the extent that the discussion is reopened, it should focus on those aspects of implementation and design that have changed since Swift 3, not the name.

Will we be providing a similar rotate(shiftingToEnd:) that performs the rotation in the opposite direction?

[citation needed]

I see a grand total of 3 posts that talk about the spelling:

One in the proposal thread by David Abrahams suggesting “rotateFirstFrom”.
One in the review thread by Dmitri Gribenko suggesting “'rotate(shiftingToStart:)”.
One immediately after that by Nate Cook agreeing that the base name should be “rotate”.

I maintain my claim that “startingAt” is a more clear and concise label than “shiftingToStart”. Compare:

rotate(startingAt: i)

rotate(shiftingToStart: i)

“Rotate this clock face starting at the three o’clock position” is analogous to rotate(startingAt: i), and has no obvious interpretation.

“Rotate this clock face so that the three o’clock position is uppermost” is analogous to rotate(shiftingToStart: i) and IMO can easily be understood.

No; there is never an element at the end position, so you can’t shift anything to the end. ;-)

The post from Dmitri is summarizing internal discussions — not all of the bikeshedding happened on the list.

I can revise the rotate proposal in fairly short order. There are implementations of all the pieces in https://github.com/apple/swift/blob/master/test/Prototypes/Algorithms.swift

I find it interesting that you changed “start” to “uppermost” in one example but not the other, dropped the word “shifting” entirely even though it is more than half of the label, and introduced “so that” out of nowhere, in attempting to demonstrate which label was more clear.

Regardless, I posit that “Rotate this clock face starting at the three o’clock position” is perfectly serviceable. If someone knows what the rotate algorithm does, they will understand what it means to apply that algorithm starting at a given index.

• • •

We could also consider labels derived from the sentence, “Rotate this clock face to start at the three o’clock position”:

rotate(toStartAt: i)

rotate(toStart: i)

rotate(startAt: i)

After all, the verb here is “rotate”—why put another verb “shift” alongside it?

I was thinking of this along the lines of gaps in between the elements where they’re being inserted, so the beginning would be right before the first element while the end would be right after the last one. Is the reason for not adding a function that performs a “right rotation” (as opposed to a “left rotation” as is currently being proposed) a naming issue, or something fundamental that I’m not getting?

What about rotate(shiftingToBeforeEnd:)?

Use case please

The idea of “right rotation” and “left rotation” make sense when you’re talking about rotating a collection by a particular number of elements. For example:

let a = [1, 2, 3, 4, 5, 6, 7]
a.rotatedLeft(by: 2)             // [3, 4, 5, 6, 7, 1, 2]
a.rotatedRight(by: 2)            // [6, 7, 1, 2, 3, 4, 5]

In this case, however, the proposed rotation isn’t by a count, it’s to rotate the elements so that the given index is now first. Those two rotations put the 2nd and 5th elements first, respectively:

a.rotated(shiftingToStart: 2)    // [3, 4, 5, 6, 7, 1, 2]
a.rotated(shiftingToStart: 5)    // [6, 7, 1, 2, 3, 4, 5]

Yeah, sure, but you get what I mean: rotate the elements so that the given index is now last (and by “last”, I mean index(before: endIndex)).

I get what you mean, but I’m not sure I get when you would need such a method. Are you asking for this so that there’s parity with a shiftingToStart version, or is there a more specific use case you have in mind?

It’s just @saagarjha’s rotate(shiftingToEnd:) idea of doing a right-rotation; we move the targeted element to the end instead of the start, acknowledging the last index is before the one-past-the-end index.

I’m envisioning that elements in each partition keep their relative order, so a right-rotation is equivalent to another left-rotation. Thinking about it while coming up with this reply, right-rotating an index x to the last valid position is the same as left-rotating c.index(after: x) to the start. So it’s a shorthand–oops, if x is already last, then the following index is an invalid position, but x’s element is already at the right spot, so this special case is the same as left-rotating the current startIndex to the start (i.e. no movement). Instead of making the user come up with that logic each time, and hopefully not mix it up, we could provide a method:

mutating func rotate(shiftingToBeforeEnd target: Index) {
    let next = index(after: target)
    guard next != endIndex else { return }
    rotate(shiftingToStart: next)
}

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.

I agree with this.
IMO, rotate(toStartAt: i) is the best of all the names proposed so far. The function proposed by @saagarjha could then be named rotate(toEndAfter: i).

It does appear that you’ve kept O(n2) for isPermutation(of:by:) and O(n) for permuteForward(by:) and permuteBackward(by:); very nice job translating the C++, by the way. If we’re looking for further optimizations, here’s what I came up with:

isPermutation(of:by:):

var myIndices = Array(indices), otherIndices = Array(other.indices)

This allocates O(n) space (and it takes O(n) time? The documentation isn’t clear on it). If we’re fine doing this, it may be worth providing specialized, faster methods when available. In particular, if Element is comparable we can sort the two Collections and then check if they’re equal in O(n log n) time, and if Element is Hashable we can do it in O(n) time by using a Dictionary.

guard myIndices.count == otherIndices.count else { return false }

Is there a reason why you put this inside the loop? Why not pull it out so it’s not evaluated every time?

permuteForward(by:), permuteBackward(by:)

let backIndices = indices.reversed()

It appears you’re creating this because you’re using it with index(where:); if we had a lastIndex(where:) I don’t think you’d need this. Something that we should add to the standard library?


One last thing, unrelated to algorithmic complexity: I’d like to include some more documentation in these methods, covering exactly what you’ve mentioned here: “short circuits if the collections are equal, have size 0” etc. so that future enhancers know what sort of guarantees to provide.

Yes, because it’s a useful method to provide–nobody wants to type out a.rotated(shiftingToStart: a.index(a.endIndex, offsetBy: -distance)). shiftingToStart shouldn’t be given preferential treatment over shiftingToEnd.