Sequence-based enumeration of permutations in lexicographic order

This is follow-up on
On Knuth's "Algorithm L" to generate permutations in lexicographic order,
where I presented the following method to enumerate all permutations of array elements
in lexicographic order:

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 = 0 && self[j] >= self[j+1] {
            j -= 1
        }
        if j == -1 {
            return false
        }

        // L3: Find last l such that 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 question is about using that method to create a Swift Sequence with all permutations, so that one can
simply enumerate these with for .. in loops and related techniques. My first approach is to use
the "type erasers" AnySequence and AnyIterator, which leads to this simple
implementation:

func permutations(of a: [T]) -> AnySequence {
    var current = a.sorted()
    var done = false
    return AnySequence {
        return AnyIterator {
            if done { return nil }
            defer { done = !current.permute() }
            return current
        }
    }
}

Example usage:

```
for p in permutations(of: [3, 2, 1]) {
print(p)
}

let allPerms = Arra

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(of a: [T]) -> AnyIterator {
    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: Sequence, IteratorProtocol {
    private var current: [T]
    private var done: Bool

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

    func makeIterator() -> PermutationSequence {
        return self
    }

    mutating func next() -> [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 : Sequence, IteratorProtocol {

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

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

    init(_ elements: S) where S.Iterator.Element == Element {
        self.current = elements.sorted()
    }

    mutating func next() -> [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() -> [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 p

StackExchange Code Review Q#158799, answer score: 9