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

[Nevin Brackett-Rozinsky]

The example implementation of the Fisher-Yates shuffle found here
<https://github.com/apple/example-package-fisheryates/blob/master/Sources/FisherYates/Fisher-Yates_Shuffle.swift>
on
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.

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