# #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!!!