How do you find this logic in Swift shuffling the elements in an array?

Question

The elements of the array 'numbers' are supposed to get shuffled in the following code. I tried to understand the logic by also inserting print statements here and there for a long time, but I have no idea after all. Can somebody kind explain this for me? Thank you.

var numbers = ["one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"]

numbers.shuffle()
dump(numbers)

extension Array {
    mutating func shuffle() {
        if count < 2 {return}
        for i in 0..<(count-1) {
            var j = 0
            while j == i {
                j = Int(arc4random_uniform(UInt32(count - i))) + i
            }
            self.swapAt(i, j)
        }
    }
}

Is your question about understanding the logic behind that function, if that function is good/bad, if there is a better function? — Larme, Mar 10 '21 at 17:53
If it's about understanding what's happening, here what you can do: put `print("Before swap: \(self.map{ "\($0)"}.joined(separator: ", "))"); print("i: \(i), j: \(j)")` just before `self.swapAt(i, j)` and `print("After swap: \(self.map{ "\($0)"}.joined(separator: ", "))")` just after. See the outputs, check the before/after logs and compare with the index i/j. — Larme, Mar 10 '21 at 17:59
@Larme, your method of how to debug using print statement is so useful. I never knew the real use of map&joined to debug arrays. The specific example really helped me compare the results visually. Thank you! — Joe K., Mar 11 '21 at 10:05

Rob · Accepted Answer · 2021-03-10T20:41:01.797

The proposed shuffling algorithm is not correct.

While biases introduced by incorrect shuffling routines are sometimes very hard to discern (it might take large number of monte carlo simulations to reveal, looking at overall statical frequencies), in this case, the resulting problem is self evident. Repeatedly build an array of Array(0..<10), shuffle it, and print the results. The non-random behavior is apparent:

[8, 2, 1, 0, 3, 4, 5, 6, 7, 9]
[8, 1, 0, 2, 3, 4, 5, 6, 7, 9]
[8, 3, 1, 2, 0, 4, 5, 6, 7, 9]
[0, 8, 1, 2, 3, 4, 5, 6, 7, 9]
[8, 3, 1, 2, 0, 4, 5, 6, 7, 9]
[8, 9, 1, 2, 3, 4, 5, 6, 7, 0]
[8, 5, 1, 2, 3, 4, 0, 6, 7, 9]
[8, 4, 1, 2, 3, 0, 5, 6, 7, 9]
[8, 5, 1, 2, 3, 4, 0, 6, 7, 9]
[0, 8, 1, 2, 3, 4, 5, 6, 7, 9]
[8, 5, 1, 2, 3, 4, 0, 6, 7, 9]
[8, 7, 1, 2, 3, 4, 5, 6, 0, 9]
[8, 5, 1, 2, 3, 4, 0, 6, 7, 9]
[8, 2, 1, 0, 3, 4, 5, 6, 7, 9]
[8, 6, 1, 2, 3, 4, 5, 0, 7, 9]
[8, 2, 1, 0, 3, 4, 5, 6, 7, 9]
[0, 8, 1, 2, 3, 4, 5, 6, 7, 9]
[8, 7, 1, 2, 3, 4, 5, 6, 0, 9]
[8, 6, 1, 2, 3, 4, 5, 0, 7, 9]
[8, 7, 1, 2, 3, 4, 5, 6, 0, 9]
[8, 5, 1, 2, 3, 4, 0, 6, 7, 9]
[8, 2, 1, 0, 3, 4, 5, 6, 7, 9]
[8, 4, 1, 2, 3, 0, 5, 6, 7, 9]
[8, 4, 1, 2, 3, 0, 5, 6, 7, 9]
[8, 7, 1, 2, 3, 4, 5, 6, 0, 9]
[8, 5, 1, 2, 3, 4, 0, 6, 7, 9]
[8, 2, 1, 0, 3, 4, 5, 6, 7, 9]
[8, 4, 1, 2, 3, 0, 5, 6, 7, 9]
[8, 7, 1, 2, 3, 4, 5, 6, 0, 9]
[0, 8, 1, 2, 3, 4, 5, 6, 7, 9]

The first serious issue is that given that j is set to 0 on every iteration of i, the while j == i { ... } obviously will not work for any i greater than 0.

Let us imagine that you fixed that issue (by replacing var j = 0 with var j = i), a less obvious issue is that implicit in that while logic is that you're effectively saying that element j must be such that i < j < n whereas the correct logic is i ≤ j < n. Effectively, you're saying that element i must be swapped with another element, whereas in a truly shuffled array, not swapping a particular element at all must be considered as an equally viable option. Frankly, a while statement is not needed, anyway.

In short, it looks like you were attempting to perform a Fisher-Yates. You can replace var j = 0 and the subsequent while loop with a single let statement:

extension Array {
    mutating func shuffle2() {
        guard count > 1 else { return }

        for i in 0 ..< count - 1 {
            let j = Int.random(in: i ..< count) // or `Int(arc4random_uniform(UInt32(count - i))) + i`
            swapAt(i, j)
        }
    }
}

Obviously, we would generally use the built in shuffling methods, shuffle, but if writing your own, j can be set with a single statement, without any while loop.

For more information see How do I shuffle an array in Swift?

I don't know how to say this 'THANK YOU'. Actually, this logic was supposed to be used in a puzzle quiz app showing only a ninth of a picture at a time. Revealing part of a picture from index 0 in order every time seems boring, so it needed some modulation. That's when this logic came in. I think your answer is so perfect to me. I learned so many things from your kind explanation. And I also appreciate your quick response! — Joe K., Mar 11 '21 at 10:03
Great. If your intent was to just shuffle, then I would suggest retiring this method entirely and use the built-in `shuffle` routine, which does a non-biased shuffle for you, and call it a day. It gets you out of the weeds of writing your own, which, as you’ve seen, is more complicated than it might appear at first blush. I only bored you with the details as I thought this might have been a programming exercise where they were testing if you knew how to do this. But using the built-in routine is easiest. — Rob, Mar 15 '21 at 07:33

How do you find this logic in Swift shuffling the elements in an array?

1 Answers1