<div dir="ltr"><div>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">found here</a> on Apple’s GitHub (and linked from <a href="https://swift.org/package-manager/">swift.org/package-manager</a>) has some problems. Stripping it down to just the Swift 4 version, the code is:</div><div><br></div><div><div><font face="monospace, monospace">public extension MutableCollection where Index == Int, IndexDistance == Int {</font></div><div><font face="monospace, monospace">    mutating func shuffle() {</font></div><div><font face="monospace, monospace">        guard count &gt; 1 else { return }</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">        for i in 0..&lt;count - 1 {</font></div><div><font face="monospace, monospace">            let j = random(count - i) + i</font></div><div><font face="monospace, monospace">            guard i != j else { continue }</font></div><div><font face="monospace, monospace">            swapAt(i, j)</font></div><div><font face="monospace, monospace">        }</font></div><div><font face="monospace, monospace">    }</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>The main issues are:</div><div><br></div><div>1) It assumes that indices are 0-based.</div><div>2) It assumes that indices can be randomly accessed by addition.</div><div><br></div><div>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><br></div><div>To fix everything, we’ll want RandomAccessCollection conformance. Once we add that, we no longer need “Index == Int”. The result looks like:</div><div><br></div><div><div><font face="monospace, monospace">public extension MutableCollection where Self: RandomAccessCollection, IndexDistance == Int {</font></div><div><font face="monospace, monospace">    mutating func shuffle() {</font></div><div><font face="monospace, monospace">        </font><span style="font-family:monospace,monospace">for n in 0 ..&lt; count-1 {</span></div><div><font face="monospace, monospace">            let i = index(startIndex, offsetBy: n)</font></div><div><font face="monospace, monospace">            let j = index(i, offsetBy: random(count-n))</font></div><div><font face="monospace, monospace">            swapAt(i, j)</font></div><div><font face="monospace, monospace">        }</font></div><div><font face="monospace, monospace">    }</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>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><br></div><div>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><br></div><div><div><font face="monospace, monospace">public extension MutableCollection {</font></div><div><font face="monospace, monospace">    mutating func shuffle() {</font></div><div><font face="monospace, monospace">        guard !isEmpty else { return }</font></div><div><font face="monospace, monospace">        </font></div><div><font face="monospace, monospace">        var idx = Array(indices)</font></div><div><font face="monospace, monospace">        </font></div><div><font face="monospace, monospace">        for i in 0 ..&lt; idx.count - 1 {</font></div><div><font face="monospace, monospace">            let j = i + random(idx.count - i)</font></div><div><font face="monospace, monospace">            swapAt(idx[i], idx[j])</font></div><div><font face="monospace, monospace">            idx.swapAt(i, j)</font></div><div><font face="monospace, monospace">        }</font></div><div><font face="monospace, monospace">    }</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>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><br></div><div>Nevin</div></div>