I needed a method to generate all permutations of given elements, so I decided toimplement Algorithm L (Lexicographic permutation generation) from Donald E. Knuth, GENERATING ALL PERMUTATIONSin 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 <= 1 {            return false        }        // L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j        // exists.        var j = count - 2        while j >= 0 && self[j] > self[j+1] {            j -= 1        }        if j == -1 {            return false        }        // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:        var l = count - 1        while 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 reducethe code, which lead to this implementation (called permute2 only to distinguish itfrom the first one):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    }}All loops are replaced by single statements which are almost self-explaining. So thislooks nice, but what about the performance?For benchmarking, the \$ 10! = 3628800 \$ permutations of 10 elements are computed:let N = 10var count = 0let start = Date()var a = Array(1...N)repeat {    count += 1} while a.permute() // or a.permute2()let end = Date()print(count, end.timeIntervalSince(start))The results (on a 1.2 GHz Intel Core m5 MacBook, compiled in Release mode) areusing the iterative permute(): 0.03 secondsusing the functional permute2(): 3 secondsi.e. the functional method is slower by a factor of 100.An alternative would be a non-mutating  method which returns the next permutationor nil:extension Array where Element: Comparable {    func nextPermutation() -> Array? {        if count <= 1 { return nil }        var j = count - 2        while j >= 0 && self[j] > self[j+1] { j -= 1 }        if j == -1 { return nil }        var a = self // Now we need a mutable copy.        var l = count - 1        while self[j] > self[l] { l -= 1 }        swap(&a[j], &a[l])        var lo = j + 1        var hi = count - 1        while lo < hi {            swap(&a[lo], &a[hi])            lo += 1            hi -= 1        }        return a    }}The benchmark for the non-mutating version islet N = 10var count = 0let start = Date()var a = Array(1...N)repeat {    count += 1    guard let b = a.nextPermutation() else { break }    a = b} while truelet end = Date()print(count, end.timeIntervalSince(start))and takes approx. 0.9 seconds on my MacBook, so this is considerably slower than themutating method permute().All feedback is welcome, in particular (but not restricted to):Naming of the methods and variables. Swifty-ness of the implementation. Iterative vs functional approach: Is it possible to use the (existing) functionalmethods without losing performance?Mutating vs. non-mutating method: Which API is clearer? Can we make the non-mutatingmethod as fast as the mutating one?Remark: I also implemented a Sequence-based enumeration, thisis posted as a separate question Sequence-based enumeration of permutations in lexicographic order.
On Knuth's Algorithm L to generate permutations in lexicographic order
performance;comparative review;swift;combinatorics
Optimising the functional approachIterative 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 sliceThe 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<Index>) {        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(uncheckedBounds:) 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 permute().Optimising first(where:)The major bottleneck here appears to be with Sequence's first(where:) method. If we take a look at its implementation, we can see it's implemented as:internal enum _StopIteration : Error {  case stop}// ...extension Sequence {  public func first(    where predicate: (Iterator.Element) throws -> Bool  ) rethrows -> Iterator.Element? {    var foundElement: Iterator.Element?    do {      try self.forEach {        if try predicate($0) {          foundElement = $0          throw _StopIteration.stop        }      }    } catch is _StopIteration { }    return foundElement  }}As first glance, this looks insane. Using forEach(_:) and a throwing a dummy Error type to exit the loop?Turns out this is an attempted optimisation by the standard library team in order to allow for sequences to implement their own version of forEach(_:) in a more efficient manner than iterating over their iterator. This is discussed in both SR-3166 and this (closed) pull request.However, unfortunately, this implementation of first(where:) is causing a big performance bottleneck for our implementation of permute(). From what I can tell, the main suspect appears to be the throwing of the _StopIteration error, which involves the wrapping in an existential Error container.A simple fix to this problem is to define our own first(where:) method that just uses a for-in loop for random-access collections. This allows us to take advantage of a more performant version of the method, while still allowing for complicated non-random-access collections to have a first(where:) implementation that uses their (potentially) customised forEach(_:) implementation.extension RandomAccessCollection {    func first(where predicate: (Iterator.Element) throws -> Bool) rethrows -> Iterator.Element? {        for element in self {            if try predicate(element) {                return element            }        }        return nil    }}This now brings my benchmark time down from ~1.45 seconds to a nice ~0.04 seconds, which is only 2x slower than your original version of permute(), but is implemented with more functional methods. For your convenience, here's a gist with all the changes that I've made.I couldn't find any other immediately obvious candidates for optimisation  but would certainly be interested if anyone else can.Mutating vs. non-mutatingWhich API is clearer?I think both are fairly clear in terms of their usage (although they will require documenting in order to inform to the user that they do the permutations lexicographically). It's often common to implement a mutating and non-mutating version of the same logic (there are lots of examples in the stdlib), as both have can their uses in different circumstances.Although for the non-mutating version, there's no need to completely re-invent the wheel  you can simply refactor it to use the mutating version's implementation:extension Array where Element : Comparable {    func nextPermutation() -> Array? {        var result = self        return result.permute() ? result : nil    }}This doesn't impact the performance due to the fact that Array has copy-on-write semantics, so the array buffer won't actually be copied unless permute() actually does a permutation.But really, for most common usages of this logic, I think the sequence-based API would probably be the clearest API to use  as I imagine most use cases will revolve around having to iterate through different permutations.Can we make the non-mutating method as fast as the mutating one?I don't believe so  if you want to have a copy of the array prior to the mutation, you'll have to pay the cost of a copy. I suspect the compiler may be able to optimise cases where the caller doesn't rely on the value of the original array remaining the same  but that's up to the compiler, and AFAIK there's no easy way to assist it with that in this case.