Sequence-based enumeration of permutations with Heap's algorithm 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&lt;Element&gt;: 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() -&gt; [Element]? {
        if firstIteration {
            firstIteration = false
        } else {
            while i &lt; c.count {
                if c[i] &lt; 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 &lt; 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.
I've been able to slash the execution time by almost half on my machine by declaring current and c as ContiguousArray:

struct HeapPermutationSequence&lt;Element&gt;: Sequence, IteratorProtocol {

    private var current: ContiguousArray&lt;Element&gt;
    private var c: ContiguousArray&lt;Int&gt;
    private var i = 0
    private var firstIteration = true

    init(elements: [Element]) {
        self.current = ContiguousArray(elements)
        self.c = ContiguousArray&lt;Int&gt;(repeating: 0, count: elements.count)
    }

    mutating func next() -&gt; ContiguousArray&lt;Element&gt;? {
        ...
    } 
}


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..&lt;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.