Sequence-based enumeration of permutations in lexicographic order
Performance

I'm not particularly surprised that the version of permutations(of:) which uses AnySequence and AnyIterator is so slow.

You're paying for the cost of both:


Heap allocation and reference counting for both the captured array and done flag.
Copy-on-write upon mutating the array in the defer block, as a copy of the array needs to be taken in order to return it to the caller prior to the mutation.


Therefore immediately you can speed things up by simply reducing the amount of closure capture – for example if you just removed the AnySequence wrapper and just returned an AnyIterator:

func permutations&lt;T: Comparable&gt;(of a: [T]) -&gt; AnyIterator&lt;[T]&gt; {
    var current = a.sorted()
    var done = false
    return AnyIterator {
        if done { return nil }
        defer { done = !current.permute() }
        return current
    }
}


You can still use an AnyIterator in a for-in loop due to the fact that it conforms to Sequence itself, and just returns itself as its own iterator. Iterating through it will 'consume' the elements returned, but you get the same behaviour by wrapping it in an AnySequence due to the fact that it's ultimately capturing the same array.

From AnySequence to AnyIterator improves my benchmark time (using the same measurement setup as shown in your question) from ~1.1 seconds to ~0.95 seconds.

However, as you note, we can do better than that by removing the closures entirely by simply declaring our own custom iterator type – PermutationSequence.


struct PermutationSequence&lt;T: Comparable&gt;: Sequence, IteratorProtocol {
    private var current: [T]
    private var done: Bool

    init(elements: [T]) {
        self.current = elements.sorted()
        self.done = false
    }

    func makeIterator() -&gt; PermutationSequence {
        return self
    }

    mutating func next() -&gt; [T]? {
        if done { return nil }
        let retval = current
        done = !current.permute()
        return retval
    }
}



This reduces my benchmark time down to ~0.75 seconds.

However, the problem with this implementation, as @dfri points out, is that we're still paying the cost of copy-on-write at each iteration due to the fact that both retval and current have a view onto the underlying array buffer.

The solution to this is fairly simple, as you noted, we return the array after the mutation has taken place, and just maintain a flag so we don't do a mutation on the first iteration. This could look like:

struct PermutationSequence&lt;Element : Comparable&gt; : Sequence, IteratorProtocol {

    private var current: [Element]
    private var firstIteration = true

    init(startingFrom elements: [Element]) {
        self.current = elements
    }

    init&lt;S : Sequence&gt;(_ elements: S) where S.Iterator.Element == Element {
        self.current = elements.sorted()
    }

    mutating func next() -&gt; [Element]? {

        // if it's the first iteration, we simply return the current array.
        if firstIteration {
            firstIteration = false
            return current
        }

        // do mutation – if the array has changed, then return it,
        // else we're at the end of the sequence.
        return current.permute() ? current : nil
    }
}


Note that I've also:


Removed the makeIterator() implementation as there's already a default implementation for this when the sequence is its own iterator.
Renamed the generic placeholder from T to Element, as it's a more descriptive name for it.
Added an init(startingFrom:) initialiser, as I suspect it will be quite useful to allow the sequence to resume from a given permutation, rather than always starting at the first.
Removed the argument label from init(elements:), as it was already clear what the initialiser does and made it take a generic Sequence input for increased flexibility.


Now we're no longer paying for the cost of an array copy at each iteration due to the fact that the iterator always has a single view onto the array's buffer (though the current property), reducing my benchmark time down to ~0.1 seconds (the target is ~0.02 seconds for directly applying permute() in repeat-while loop).

The key to achieving the target performance weirdly appears to be avoiding having multiple exits in the implementation of next().

If we refactor the iterator's next() method like this, so that there's only one return:

mutating func next() -&gt; [Element]? {

    var continueIterating = true

    // if it's the first iteration, we avoid doing the permute() and reset the flag.
    if firstIteration {
        firstIteration = false
    } else {
        continueIterating = current.permute()
    }

    // if the array changed (and it isn't the first iteration), then return it,
    // else we're at the end of the sequence.
    return continueIterating ? current : nil
}


we are able to achieve the desired benchmark time of ~0.02 seconds. Exactly why this reduces the time so dramatically, I'm not too sure – it appears that having multiple points of exit in the method prevents the compiler from performing some important optimisation.

It also appears to be related to inlining, as when marking the next() method with the @inline(never) attribute, the use of an additional return has no significant impact on the performance. I'd certainly be interested if anyone else knows more about exactly what's going on here.

Regarding your comment about making shouldContinue (renamed to continueIterating here) a let constant – I could not observe a difference in performance in doing so, so I left it as a var.

Separating the sequence and iterator

Depending on your usage, it may be useful to separate your permutation sequence implementation from its iterator in order to allow for non-destructive iteration (this isn't required for a sequence, but can be useful in places).

This would just be as simple as having the sequence keep its own constant copy of the array prior to mutation, which gets passed to the iterator on its creation.

In Swift 3.1, this can be expressed rather nicely with a nested generic type:

struct PermutationSequence&lt;Element : Comparable&gt; : Sequence {

    // constant copy of the elements to pass to the iterator on its creation.
    let elements: [Element]

    init(startingFrom elements: [Element]) {
        self.elements = elements
    }

    init&lt;S : Sequence&gt;(_ elements: S) where S.Iterator.Element == Element {
        self.elements = elements.sorted()
    }

    struct Iterator : IteratorProtocol {

        private var current: [Element]
        private var firstIteration = true

        // you should create a PermutationSequence rather than invoking this
        // initialiser directly.
        fileprivate init(startingFrom elements: [Element]) {
            self.current = elements
        }

        mutating func next() -&gt; [Element]? {

            var continueIterating = true

            // if it's the first iteration, we avoid doing the permute() and reset the flag
            if firstIteration {
                firstIteration = false
            } else {
                continueIterating = current.permute()
            }

            // if the array changed (and it isn't the first iteration), then return it,
            // else we're at the end of the sequence.
            return continueIterating ? current : nil
        }
    }

    func makeIterator() -&gt; Iterator {
        return Iterator(startingFrom: elements)
    }
}


This shouldn't adversely affect the performance in any way (benchmarking doesn't reveal any significant difference) – an initial copy of the array may have to be taken upon the first mutation, but that's also true for the previous version of PermutationSequence due to the fact that the caller has a view onto the array buffer.