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

[Saagar Jha]

Saagar Jha

> On Dec 16, 2017, at 16:34, Nevin Brackett-Rozinsky via swift-users <swift-users at swift.org> wrote:
> 
> 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 <https://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.

Actually, I believe the first guard is still necessary–if the collection is empty, you’d end up with trying to construct the range 0..<-1, which traps. Alternatively, stride(from:to) is more lenient.

> 
> 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
> _______________________________________________
> swift-users mailing list
> swift-users at swift.org
> https://lists.swift.org/mailman/listinfo/swift-users

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