#StackBounty: #performance #comparative-review #swift #combinatorics On Knuth's "Algorithm L" to generate permutations in…

Bounty: 50

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.


Get this bounty!!!