<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><br class=""><div class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Saagar Jha</div>
</div>
<div><br class=""><blockquote type="cite" class=""><div class="">On Dec 16, 2017, at 16:34, Nevin Brackett-Rozinsky via swift-users <<a href="mailto:swift-users@swift.org" class="">swift-users@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="">The example implementation of the Fisher-Yates shuffle <a href="https://github.com/apple/example-package-fisheryates/blob/master/Sources/FisherYates/Fisher-Yates_Shuffle.swift" class="">found here</a> on Apple’s GitHub (and linked from <a href="https://swift.org/package-manager/" class="">swift.org/package-manager</a>) has some problems. Stripping it down to just the Swift 4 version, the code is:</div><div class=""><br class=""></div><div class=""><div class=""><font face="monospace, monospace" class="">public extension MutableCollection where Index == Int, IndexDistance == Int {</font></div><div class=""><font face="monospace, monospace" class=""> mutating func shuffle() {</font></div><div class=""><font face="monospace, monospace" class=""> guard count > 1 else { return }</font></div><div class=""><font face="monospace, monospace" class=""><br class=""></font></div><div class=""><font face="monospace, monospace" class=""> for i in 0..<count - 1 {</font></div><div class=""><font face="monospace, monospace" class=""> let j = random(count - i) + i</font></div><div class=""><font face="monospace, monospace" class=""> guard i != j else { continue }</font></div><div class=""><font face="monospace, monospace" class=""> swapAt(i, j)</font></div><div class=""><font face="monospace, monospace" class=""> }</font></div><div class=""><font face="monospace, monospace" class=""> }</font></div><div class=""><font face="monospace, monospace" class="">}</font></div></div><div class=""><br class=""></div><div class="">The main issues are:</div><div class=""><br class=""></div><div class="">1) It assumes that indices are 0-based.</div><div class="">2) It assumes that indices can be randomly accessed by addition.</div><div class=""><br class=""></div><div class="">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²).</div><div class=""><br class=""></div><div class="">To fix everything, we’ll want RandomAccessCollection conformance. Once we add that, we no longer need “Index == Int”. The result looks like:</div><div class=""><br class=""></div><div class=""><div class=""><font face="monospace, monospace" class="">public extension MutableCollection where Self: RandomAccessCollection, IndexDistance == Int {</font></div><div class=""><font face="monospace, monospace" class=""> mutating func shuffle() {</font></div><div class=""><font face="monospace, monospace" class=""> </font><span style="font-family:monospace,monospace" class="">for n in 0 ..< count-1 {</span></div><div class=""><font face="monospace, monospace" class=""> let i = index(startIndex, offsetBy: n)</font></div><div class=""><font face="monospace, monospace" class=""> let j = index(i, offsetBy: random(count-n))</font></div><div class=""><font face="monospace, monospace" class=""> swapAt(i, j)</font></div><div class=""><font face="monospace, monospace" class=""> }</font></div><div class=""><font face="monospace, monospace" class=""> }</font></div><div class=""><font face="monospace, monospace" class="">}</font></div></div><div class=""><br class=""></div><div class="">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.</div></div></div></blockquote><div><br class=""></div>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.</div><div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">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:</div><div class=""><br class=""></div><div class=""><div class=""><font face="monospace, monospace" class="">public extension MutableCollection {</font></div><div class=""><font face="monospace, monospace" class=""> mutating func shuffle() {</font></div><div class=""><font face="monospace, monospace" class=""> guard !isEmpty else { return }</font></div><div class=""><font face="monospace, monospace" class=""> </font></div><div class=""><font face="monospace, monospace" class=""> var idx = Array(indices)</font></div><div class=""><font face="monospace, monospace" class=""> </font></div><div class=""><font face="monospace, monospace" class=""> for i in 0 ..< idx.count - 1 {</font></div><div class=""><font face="monospace, monospace" class=""> let j = i + random(idx.count - i)</font></div><div class=""><font face="monospace, monospace" class=""> swapAt(idx[i], idx[j])</font></div><div class=""><font face="monospace, monospace" class=""> idx.swapAt(i, j)</font></div><div class=""><font face="monospace, monospace" class=""> }</font></div><div class=""><font face="monospace, monospace" class=""> }</font></div><div class=""><font face="monospace, monospace" class="">}</font></div></div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">Nevin</div></div>
_______________________________________________<br class="">swift-users mailing list<br class=""><a href="mailto:swift-users@swift.org" class="">swift-users@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-users<br class=""></div></blockquote></div><br class=""></body></html>