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.