14
\$\begingroup\$

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 <= 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 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 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 this looks nice, but what about the performance?

For benchmarking, the \$ 10! = 3628800 \$ permutations of 10 elements are computed:

let N = 10
var count = 0
let 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) are

  • using the "iterative" permute(): 0.03 seconds
  • using the "functional" permute2(): 3 seconds

i.e. the functional method is slower by a factor of 100.

An alternative would be a non-mutating method which returns the next permutation or 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 is

let N = 10
var count = 0
let start = Date()
var a = Array(1...N)
repeat {
    count += 1
    guard let b = a.nextPermutation() else { break }
    a = b
} while true
let end = Date()
print(count, end.timeIntervalSince(start))

and takes approx. 0.9 seconds on my MacBook, so this is considerably slower than the mutating 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) functional methods without losing performance?
  • Mutating vs. non-mutating method: Which API is clearer? Can we make the non-mutating method as fast as the mutating one?

Remark: I also implemented a Sequence-based enumeration, this is posted as a separate question Sequence-based enumeration of permutations in lexicographic order.

\$\endgroup\$
  • \$\begingroup\$ I haven't really looked into any of this in detail yet (not at my Mac), but at the top of my head, a minor detail: in the condition of the while loop at L2 in (the already high-performant) permute(), could switching from using the lazy rhs-@autoclosure wrapping && operator to e.g. while j >= 0 ? self[j] > self[j+1] : false affect the performance in any way? \$\endgroup\$ – dfri Mar 29 '17 at 15:34
  • \$\begingroup\$ @dfri: No, it does not change the performance in a noticeable way. \$\endgroup\$ – Martin R Mar 29 '17 at 16:12
  • \$\begingroup\$ hello are you able to post some more information about knuth's algorithm and what it is intending to do ? \$\endgroup\$ – BKSpurgeon Mar 30 '17 at 11:04
  • 1
    \$\begingroup\$ @MartinR thx for the link \$\endgroup\$ – muescha Mar 30 '17 at 11:57
  • 1
    \$\begingroup\$ @muescha Here's a PDF version of fasc2b: PDF. (Algorithm L is on page 1.) (Although I wonder what system you have that cannot handle gzip and postscript…) \$\endgroup\$ – ShreevatsaR May 21 '17 at 1:57
10
+50
\$\begingroup\$

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<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(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 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-mutating

Which 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.

\$\endgroup\$
  • \$\begingroup\$ Most interesting observations wrt first(where:)! I wonder that the performance issue was never discussed in SR-3166. \$\endgroup\$ – Martin R Apr 1 '17 at 15:37
  • \$\begingroup\$ @MartinR Yeah, I'm stumped. I can only assume they didn't do extensive testing with the different versions, as when testing the two implementations with a low number repeated calls to them (but on large sequences), they do exhibit similar performance. It's only with a high number of repeated calls where the performance difference really stands out. It's probably worth adding a comment to the bug report noting this (I can do this later if you want – but right now I really need to get on with some work :P). \$\endgroup\$ – Hamish Apr 1 '17 at 15:58
2
\$\begingroup\$

Improving L2

There is an imperfection in the iterative approach: N! - 1 useless checks whether j equals -1 (in an already sorted array, in an ascending order).

A quicker way would be the following :

while self[j] >= self[j+1] {
    if j > 0 {
        j -= 1
    }
    else {
        return false
    }
}

(Note that the most probable condition is placed first for )

In my benchmarks, the original takes ~0.062s and the improved version takes ~0.055s which translates to an almost 12% speed up.


Improving L3

self[j] is accessed too many times, and it is a two-step read: reading j, then accessing self at j. Better store it in a variable and then it would be a one-step read :

var l = count - 1
let jElement = self[j]
while jElement >= self[l] {
    l -= 1
}
self.swapAt(j, l)

Which brings the execution time down to ~0.043s (30% faster than the original).


Zigzagging

The idea is: we still have to read cells between l - 1 and j twice, hence the name of this section. If only we could read each cell once!

This goal is still not attained since self[j] is read twice in the following snippet. It has gained up to ~4ms vis-a-vis the version having the previous improvements :

var tempo = self[j+1]
while self[j] >= tempo {
    if j > 0 {
        tempo = self[j]
        j -= 1
    }
    else {
        return false
    }
}

The only explanation I could find/guess for this (slight) improvement, is that it avoids the unnecessary number of additions : j+1. That number is given by the following sequence : $$ u_{3} = 4; u_{2} = 2; u_{1} = u_{0} = 0 $$ $$ u_{n} = n . u_{n-1} + 1 ; n \geq 4 $$

For n = 10, the number of additions is 2,606,501.


The following code was used for benchmarking in this section:

class TestClass {
    let tag: Int
    init(t: Int) {
        self.tag = t
    }
}

extension TestClass: Comparable {
    static func == (lhs: TestClass, rhs: TestClass) -> Bool {
        return lhs.tag == rhs.tag
    }
    static func < (lhs: TestClass, rhs: TestClass) -> Bool {
        return lhs.tag < rhs.tag
    }
}

var a: [TestClass] = Array(1...10).map { TestClass(t: $0) }

let N = 10
var count = 0
let start = Date()
repeat {
    count += 1
} while a.permute()
let end = Date()
print(count, end.timeIntervalSince(start))

The edge given by this improvement is valid for an array of value types too.


Final version

For convenience, here is the version with all improvements:

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
    var tempo = self[j+1]
    while self[j] >= tempo {
        if j != 0 {
            tempo = self[j]
            j -= 1
        }
        else {
            return false
        }
    }

    // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
    var l = count - 1
    let jElement = self[j]
    while jElement >= self[l] {
        l -= 1
    }
    self.swapAt(j, l)

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

Other

In the benchmarking code, creating the array a isn't part of the algorithm, and shouldn't be sandwiched between the start and end dates.

\$\endgroup\$
  • 1
    \$\begingroup\$ I can confirm that with your modification it is 10-15% faster than my original code. \$\endgroup\$ – Martin R Dec 1 '18 at 16:32
  • \$\begingroup\$ @MartinR I would be interested if zigzagging through the array could be avoided, but I doubt it. \$\endgroup\$ – ielyamani Dec 7 '18 at 23:12
1
\$\begingroup\$

The code works correctly – but only if the array elements are mutually different. For arrays with repeated elements, such as ["a", "a", "b"], it leads to an infinite loop. (This is – of course – handled correctly in Knuth's "Algorithm L", the problem is only in the above implementation).

It can be fixed by changing the comparison operators in the steps L2 and L3 from > to >=:

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
}

Example:

var a = [1, 1, 2]
repeat {
    print(a)
} while a.permute()

Output:

[1, 1, 2]
[1, 2, 1]
[2, 1, 1]

The same applies to the permute2() method, where replacing <= by < makes it work with arbitrary arrays.


Remark: For Swift 4 one has to replace the swap() invocations by the swapAt() method of the MutableCollection protocol (compare SE-0173 Add MutableCollection.swapAt(_:_:)). For example,

swap(&self[j], &self[l])

becomes

self.swapAt(j, l)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.