[swift-users] Incorrect Fisher-Yates shuffle in example code

Nevin Brackett-Rozinsky nevin.brackettrozinsky at gmail.com
Sat Dec 16 18:34:30 CST 2017

The example implementation of the Fisher-Yates shuffle found here
Apple’s GitHub (and linked from swift.org/package-manager) has some
problems. Stripping it down to just the Swift 4 version, the code is:

public extension MutableCollection where Index == Int, IndexDistance == Int
    mutating func shuffle() {
        guard count > 1 else { return }

        for i in 0..<count - 1 {
            let j = random(count - i) + i
            guard i != j else { continue }
            swapAt(i, j)

The main issues are:

1) It assumes that indices are 0-based.
2) It assumes that indices can be randomly accessed by addition.

The former means it does not work for ArraySlice, and the latter means it
won’t work for all custom types. Additionally, the “count” property (which
is only guaranteed to be O(n) here) is accessed inside the loop, thus
making the algorithm potentially O(n²).

To fix everything, we’ll want RandomAccessCollection conformance. Once we
add that, we no longer need “Index == Int”. The result looks like:

public extension MutableCollection where Self: RandomAccessCollection,
IndexDistance == Int {
    mutating func shuffle() {
        for n in 0 ..< count-1 {
            let i = index(startIndex, offsetBy: n)
            let j = index(i, offsetBy: random(count-n))
            swapAt(i, j)

Both of the original guard statements would be superfluous here (notably,
“swapAt” is documented to have no effect when i and j are the same) so I
removed them.

Technically we could get away without random access and still have an O(n)
algorithm, at the cost of copying the indices to an array:

public extension MutableCollection {
    mutating func shuffle() {
        guard !isEmpty else { return }

        var idx = Array(indices)

        for i in 0 ..< idx.count - 1 {
            let j = i + random(idx.count - i)
            swapAt(idx[i], idx[j])
            idx.swapAt(i, j)

In any event, just in case someone was using a cut-and-paste version of the
example code in their own project, now you know it needs adjustment.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20171216/c065d886/attachment.html>

More information about the swift-users mailing list