你如何在 Swift 中找到这个逻辑来洗牌数组中的元素？

Question

数组 'numbers' 的元素应该在以下代码中打乱顺序。我试图通过在这里和那里插入打印语句来理解逻辑很长一段时间，但我毕竟不知道。有人可以帮我解释一下吗？谢谢。

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)
        }
    }
}

Answer 1

建议的改组算法不正确。

虽然不正确的洗牌程序引入的偏差有时很难辨别（可能需要大量 monte carlo 模拟才能揭示，查看整体静态频率），在这种情况下，由此产生的问题是自明显。重复构建一个 Array(0..<10) 的数组，将其打乱，并打印结果。非随机行为很明显：

[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]

第一个严重的问题是，鉴于 j 在 i 的每次迭代中都设置为 0，while j == i { ... } 显然不适用于任何 i 大于 0.

让我们假设您解决了该问题（通过将 var j = 0 替换为 var j = i），一个不太明显的问题是 while 逻辑中隐含的是您有效说元素 j 必须是 i < j < n 而正确的逻辑是 i ≤ j < n。实际上，您是说元素 i 必须与另一个元素交换，而在真正混洗的数组中，根本不交换特定元素必须被视为同等切实可行的选项。坦率地说，无论如何都不需要 while 声明。

简而言之，您似乎在尝试执行 Fisher-Yates。您可以用单个 let 语句替换 var j = 0 和随后的 while 循环：

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)
        }
    }
}

显然，我们通常会使用内置的洗牌方法，shuffle，但是如果自己编写，j 可以用一条语句设置，没有任何 while 循环.

有关详细信息，请参阅 How do I shuffle an array in Swift?

你如何在 Swift 中找到这个逻辑来洗牌数组中的元素？

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

algorithm

logic

swift