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

[Saagar Jha]

While we’re still looking at the Fisher-Yates shuffle package, I stumbled upon this <https://github.com/apple/example-package-fisheryates/blob/master/Sources/FisherYates/random.swift#L18> definition of random():

 public let random: (Int) -> Int = {
     while true {
        let x = Glibc.random() % $0
        let y = Glibc.random() % $0
        guard x == y else { return x }
    }
}

Perhaps I’m mistaken here, but if this is random(3) <https://developer.apple.com/legacy/library/documentation/Darwin/Reference/ManPages/man3/random.3.html> don’t we have to 1. seed it before use and 2. deal with modulo bias? I’m also not quite sure why the guard is there, either.

Saagar Jha

> On Dec 16, 2017, at 16:37, Daniel Dunbar via swift-users <swift-users at swift.org> wrote:
> 
> Would you like to post a PR to fix these issues?
> 
>  - Daniel
> 
>> On Dec 16, 2017, at 4:34 PM, Nevin Brackett-Rozinsky via swift-users <swift-users at swift.org <mailto: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.
>> 
>> 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 <mailto:swift-users at swift.org>
>> https://lists.swift.org/mailman/listinfo/swift-users
> 
> _______________________________________________
> 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/1e16b1fa/attachment.html>