On Knuth's "Algorithm L" to generate permutations in lexicographic order

I needed a method to generate all permutations of given elements, so I decided to
implement "Algorithm L (Lexicographic permutation generation)" from
Donald E. Knuth, "GENERATING ALL PERMUTATIONS"
in Swift. The labels L2, L3, L4 refer to the steps in Knuth's algorithm:

extension Array where Element: Comparable {

    /// Replaces the array by the next permutation of its elements in lexicographic
    /// order.
    ///
    /// It uses the "Algorithm L (Lexicographic permutation generation)" from
    ///    Donald E. Knuth, "GENERATING ALL PERMUTATIONS"
    ///    http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
    ///
    /// - Returns: `true` if there was a next permutation, and `false` otherwise
    ///   (i.e. if the array elements were in descending order).

    mutating func permute() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count = 0 && self[j] > self[j+1] {
            j -= 1
        }
        if j == -1 {
            return false
        }

        // L3: Find last l such that self[j]  self[l] {
            l -= 1
        }
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            swap(&self[lo], &self[hi])
            lo += 1
            hi -= 1
        }
        return true
    }
}

This worked correctly in all my tests, here is a simple example:

do {
    var a = ["a", "b", "c"]
    repeat {
        print(a)
    } while a.permute()
}

Output:

["a", "b", "c"]
["a", "c", "b"]
["b", "a", "c"]
["b", "c", "a"]
["c", "a", "b"]
["c", "b", "a"]

Then I tried to utilize existing methods from the Swift standard library to reduce
the code, which lead to this implementation (called permute2 only to distinguish it
from the first one):

```
extension Array where Element: Comparable {

mutating func permute2() -> Bool {

// Nothing to do for empty or single-element arrays:
if

Optimising the functional approach


Iterative vs functional approach: Is it possible to use the (existing) functional methods without losing performance?

I don't think it's possible to use the standard library's existing collection methods without losing performance here – as I go onto investigate, there are quite a few inefficiencies with them. We can however make quite a few improvements by defining methods of our own to bring the performance close to the iterative approach.

For your implementation of the mutable version of permute() that uses the existing standard library collection methods:

extension Array where Element: Comparable {

    mutating func permute2() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
        // exists.
        guard let j = indices.reversed().dropFirst()
            .first(where: { self[$0] <= self[$0 + 1] })
        else { return false }

        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
        let l = indices.reversed()
            .first(where: { self[j] <= self[$0] })!
        swap(&self[j], &self[l])

        // L4: Reverse elements j+1 ... count-1:
        replaceSubrange(j+1..<count, with: self[j+1..<count].reversed())
        return true
    }
}

This gives me a benchmark time down of ~2.65 seconds (running it with a Swift 3.1 -O build). Here's some improvements we can make to reduce this time...

Reversing a slice

The first thing that stands out to me is the line:

replaceSubrange(j+1..<count, with: self[j+1..<count].reversed())

The problem with this is that self[j+1..<count].reversed() returns a reversed view onto the ArraySlice – which in turn has a view onto the array's buffer. Therefore when you come to call replaceSubrange, the array's buffer is not uniquely referenced. This therefore forces a copy of the array, which is a costly operation to be doing at every call of permute().

One nice syntactic (and a slight performance) improvement over this would be to instead call reverse() on the ArraySlice itself:

self[j + 1 ..< count].reverse()

Note that I've added whitespace around the binary operators, which I think makes it much more readable.

Performance-wise this is slightly better because we're now mutating (a temporary) ArraySlice, before re-assigning it to back to Array's subscript – therefore now only the slice itself needs to be copied (not the entire array).

This brings my benchmark time down from ~2.65 seconds to ~2.06 seconds.

However, we're still doing an unnecessary copy (although really I think the compiler should be able optimise this away and mutate the array directly – but this doesn't currently appear to be the case).

One way in order to allow us to mutate the array directly, rather than going through ArraySlice is to simply define a method to reverse the elements of an array between two given indices:

extension Array {

    /// Reverses the elements of the collection within a given range of indices.
    ///
    /// - Parameter indices: A range of valid indices of the collection,
    ///  the elements of which will be reversed.
    ///
    mutating func reverse(indices: Range) {

        if indices.isEmpty { return }

        var low = indices.lowerBound
        var high = index(before: indices.upperBound)

        while low < high {
            swap(&self[low], &self[high])
            formIndex(after: &low)
            formIndex(before: &high)
        }
    }
}

This implementation is based off the standard library's own reverse() method. Note that it may be more natural to express the indices parameter as a ClosedRange, due to the fact that the range should never be empty – however for increased interoperability, I would simply suggest adding this as another overload for this, if desired.

It's also worth noting that in practise, I would consider defining this as an extension of
MutableCollection where Self : BidirectionalCollection, rather than Array. However, unfortunately, it appears to compiler is unable to specialise its implementation when doing so, which leads to reduced performance.

But regardless of these details, now we can say:

reverse(indices: j + 1 ..< count)

Which brings my benchmark time down from ~2.06 seconds to ~1.46 seconds.

If we're going for maximal performance here, we can also use Range's init(unchecked​Bounds:​) initialiser to skip the precondition check that lowerBound <= upperBound, given that we know
j + 1 < count (as the maximum value of j is count - 2).

reverse(indices: Range(uncheckedBounds: (lower: j + 1, upper: count)))

This brings my benchmark time down from ~1.46 seconds to ~1.45 seconds. However, we're still way off the target benchmark time of ~0.02 seconds for your original mutating version of `per

StackExchange Code Review Q#158798, answer score: 11