*Bounty: 50*

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