Sequence-based enumeration of permutations with Heap's algorithm

Question

Heap's algorithm is an algorithm to generate all permutations of a given array. It

... generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed.

Here is my attempt to implement this algorithm in Swift 4 as a Sequence, so that all permutations of an array can be enumerated with for .. in loops and related techniques:

/* * A sequence of all permutations of a given array. Based on the * non-recursive version of Heap's algorithm as described in * https://en.wikipedia.org/wiki/Heap%27s_algorithm */ struct HeapPermutationSequence<Element>: Sequence, IteratorProtocol { private var current: [Element] private var c: [Int] private var i = 0 private var firstIteration = true init(elements: [Element]) { self.current = elements self.c = Array(repeating: 0, count: elements.count) } mutating func next() -> [Element]? { if firstIteration { firstIteration = false } else { while i < c.count { if c[i] < i { if i % 2 == 0 { current.swapAt(0, i) } else { current.swapAt(c[i], i) } c[i] += 1 i = 0 break } else { c[i] = 0 i += 1 } } } return i < c.count ? current : nil } } 

Example usage:

for p in HeapPermutationSequence(elements: [1, 2, 3]) { print(p, terminator: ", ") } print() // Output: // [1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1], 

Several techniques from @Hamish's answer Sequence-based enumeration of permutations in lexicographic order could be applied here as well to improve the performance:

• Avoid the cost of copy-on-write by not mutating the current array after it is returned as the next element.
• Have a single exit point in the next() method.

Benchmark:

let N = 10 var count = 0 let start = Date() for _ in HeapPermutationSequence(elements: Array(1...N)) { count += 1 } let end = Date() print(count, end.timeIntervalSince(start)) 

which takes about 0.03 seconds (on a 1.2 GHz Intel Core m5 MacBook, compiled in Release mode).

All feedback is welcome, such as (but of course not restricted to):

• Performance improvements.
• Better variable names (c and i are simply copied from the Wikipedia pseudo-code).
• Simplifying the code, or making it better readable/understandable.

Answer 1

I've been able to slash the execution time by almost half on my machine by declaring current and c as ContiguousArray:

struct HeapPermutationSequence<Element>: Sequence, IteratorProtocol { private var current: ContiguousArray<Element> private var c: ContiguousArray<Int> private var i = 0 private var firstIteration = true init(elements: [Element]) { self.current = ContiguousArray(elements) self.c = ContiguousArray<Int>(repeating: 0, count: elements.count) } mutating func next() -> ContiguousArray<Element>? { ... } } 

Benchmarks

Using the same benchmarking code, compiled with -O in the terminal, on a 2.7 GHz i7 MacBook Pro :

• Before: fluctuates between 0.126s and 0.139s
• After: 0.07s with inferior fluctuations, thanks to current being a ContiguousArray, since such a type has predictable performance.

---

I've got to 0.022s by wrapping the benchmarking code in a do statement or any new scope (Makes the code 3x faster):

do { let N = 10 var count = 0 let start = mach_absolute_time() for _ in HeapPermutationSequence(elements: Array(1...N)) { count += 1 } let end = mach_absolute_time() print(count, Double(end - start)/Double(1e9)) } 

🤯 Putting the original code inside a single iteration for loop for _ in 0..<1 {...} brings its execution time down to 0.020 too. Putting it inside a do statement, repeat while false, closure, while true { ... break}..., takes it back to 0.13s 👎🏻.

N.B: The above result has only been observed on a mac (4 physical cores, 4 logical ones). On an iPhone and an iPad (both 2 physical cores), using a ContiguousArray makes the code a full second faster (2.~s vs 3.~s).

---

We can gain 1 to 2ms by rearranging the conditions:

private var notFirstIteration: Bool = false //... if notFirstIteration { //... } else { notFirstIteration = true } 

This would eliminate The (N! - 1) unnecessary conditional jumps in the assembly code.

---

As suggested by Mr. Martin: Not discarding manually the output of HeapPermutationSequence by using this code:

for x in HeapPermutationSequence(elements: Array(1...N)) { count += x.count } 

Gives a +/-2ms fluctuation in both solutions.

Answer 2

HeapPermutationSequence computes all permutations of a given array. A common Swift idiom is not to operate on concrete types, but on protocols. In this case, we need a mutable collection type which allows efficient random access to its elements. Therefore it makes sense to implement

struct HeapPermutationSequence<C>: Sequence, IteratorProtocol where C: RandomAccessCollection & MutableCollection { init(elements: C) { ... } mutating func next() -> C? { ... } } 

instead, which is then applicable to more types. A simple example is an array slice:

let slice = [1, 2, 3, 4, 5].prefix(3) for p in HeapPermutationSequence(elements: slice) { print(p) } 

There is not much that needs to be changed, only the index calculations become a bit verbose:

struct HeapPermutationSequence<C>: Sequence, IteratorProtocol where C: RandomAccessCollection & MutableCollection { private var current: C private var c: [Int] private var i = 0 private var firstIteration = true init(elements: C) { self.current = elements self.c = Array(repeating: 0, count: elements.count) } mutating func next() -> C? { if firstIteration { firstIteration = false } else { while i < c.count { if c[i] < i { if i % 2 == 0 { current.swapAt(current.startIndex, current.index(current.startIndex, offsetBy: i)) } else { current.swapAt(current.index(current.startIndex, offsetBy: c[i]), current.index(current.startIndex, offsetBy: i)) } c[i] += 1 i = 0 break } else { c[i] = 0 i += 1 } } } return i < c.count ? current : nil } } 

In my tests, the benchmark still runs in the same time with this implementation.