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.
whileloop atL2in (the already high-performant)permute(), could switching from using the lazyrhs-@autoclosurewrapping&&operator to e.g.while j >= 0 ? self[j] > self[j+1] : falseaffect the performance in any way? \$\endgroup\$