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

[Nevin Brackett-Rozinsky]

…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.

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20171218/7396607a/attachment.html>