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

[Ankit Aggarwal]

Thank you for working on this!

On Sun, Dec 17, 2017 at 11:07 PM, Saagar Jha via swift-users <
swift-users at swift.org> wrote:

>
> Saagar Jha
>
> On Dec 17, 2017, at 22:24, Nevin Brackett-Rozinsky via swift-users <
> swift-users at swift.org> wrote:
>
> …well that was more complicated than I anticipated.
>
> The “random” function was (Int) -> Int, so when I removed the
> “IndexDistance == Int” constraint on “shuffle” I either had to add several
> “numericCast” calls or make “random” generic.
>
> So I made “random” generic. And also fixed the modulo bias issue in the
> Glibc version that Saagar mentioned. Or at least I hope I did. I haven’t
> tested that part (nor any of the non-Swift-4 / non-macOS parts). Also, I am
> not sure why “random” had been a closure value stored in a “let” constant,
> but I changed it to a function.
>
>
> Great! I'll close my pull request, then.
>
>
> While I was at it, I removed the random-access constraint I had placed on
> “shuffle”. It will now shuffle any MutableCollection, with complexity O(n)
> for a RandomAccessCollection and O(n²) otherwise. (The constraint was
> different in different Swift versions, so the entire extension had to be
> duplicated. Without the constraint the implementation is much sleeker.)
>
> Nevin
>
>
> On Sun, Dec 17, 2017 at 9:26 PM, Nevin Brackett-Rozinsky <
> nevin.brackettrozinsky at gmail.com> wrote:
>
>> On Sun, Dec 17, 2017 at 7:37 PM, Dave Abrahams <dabrahams at apple.com>
>> wrote:
>>
>>>
>>> On Dec 16, 2017, at 4:34 PM, Nevin Brackett-Rozinsky via swift-users <
>>> swift-users at swift.org> wrote:
>>>
>>> public extension MutableCollection where Self: RandomAccessCollection,
>>> IndexDistance == Int {
>>>
>>>
>>> IndexDistance == Int is an over-constraint, FWIW.  Adding it is
>>> generally a mistake.  Not a serious one, but it does limit utility somewhat.
>>>
>>> HTH,
>>> Dave
>>>
>>
>> You are correct, however there is an accepted-and-implemented proposal (
>> SE–0191
>> <https://github.com/apple/swift-evolution/blob/master/proposals/0191-eliminate-indexdistance.md>)
>> to eliminate IndexDistance and replace it with Int, so the constraint will
>> always be satisfied starting in Swift 4.1.
>>
>> I wrote a version of shuffle() without that constraint, but it is less
>> elegant: the line “for n in 0 ..< count - 1” no longer compiles, and
>> writing “0 as IndexDistance” doesn’t fix it because the resulting Range is
>> not a Sequence, since IndexDistance.Stride does not conform to
>> SignedInteger (at least in Swift 4.0 according to Xcode 9.2).
>>
>> A while loop works of course, though a direct conversion requires writing
>> “var n = 0 as IndexDistance” before the loop. Luckily, with a bit of
>> cleverness we can eliminate all mention of IndexDistance, and this time we
>> really and truly don’t need the “guard !isEmpty” line:
>>
>> extension MutableCollection where Self: RandomAccessCollection {
>>     mutating func shuffle() {
>>         var n = count
>>         while n > 1 {
>>             let i = index(startIndex, offsetBy: count - n)
>>             let j = index(i, offsetBy: random(n))
>>             n -= 1
>>             swapAt(i, j)
>>         }
>>     }
>> }
>>
>> Essentially, the constraint is there to make the code nicer on pre-4.1
>> versions of Swift, though I’m happy to remove it if you think that’s
>> better. If nothing else, removing the constraint means people reading the
>> example code in the future won’t be misled into thinking they need to use
>> it themselves, so perhaps it should go just on that account.
>>
>> Okay, you’ve convinced me, I’ll update the PR. :-)
>>
>> Nevin
>>
>
> _______________________________________________
> swift-users mailing list
> 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/20171218/1825ecc5/attachment.html>