为什么渔民耶茨最有用的洗牌算法？

问题描述

你会说现代版渔民耶茨是最公正的洗牌算法？你会如何​​解释该阵列中的每个元件具有原文光斑1 / n是一个概率是多少？

Would you say modern version of fisher yates is the most unbiased shuffling algorithm?How would you explain that each element in the array has a probability of 1/n being in its original spot?

推荐答案

给出一个完美的伪随机数生成器（在梅森倍捻机非常接近），费雪耶茨算法在每一个排列有发生的概率相等完全公正的。这是很容易证明使用感应。费雪耶茨算法可以写成递归如下（以Python语法伪code）：

Given a perfect pseudo-random number generator (the Mersenne Twister is very close), the Fisher-Yates algorithm is perfectly unbiased in that every permutation has an equal probability of occurring. This is easy to prove using induction. The Fisher-Yates algorithm can be written recursively as follows (in Python syntax pseudocode):

def fisherYatesShuffle(array):
    if len(array) < 2:
        return

    firstElementIndex = uniform(0, len(array))
    swap(array[0], array[firstElementIndex])
    fisherYatesShuffle(array[1:])

每个指数都有被选定为 firstElementIndex 的概率相同。当你递归，你现在选择任何仍留元素的概率相同。

Each index has an equal probability of being selected as firstElementIndex. When you recurse, you now have an equal probability of choosing any of the elements that are still left.

编辑：算法已数学证明是公正的。由于该算法具有不确定性，最好的方法来测试执行是否正常是统计学。我将采取的一些任意的，而是小尺寸的阵列，它洗一束倍（从每次相同的置换作为输入）和计数的各输出置换发生的次数。然后，我会使用 Pearson的卡方检验以测试这个分布的均匀性。

The algorithm has been mathematically proven to be unbiased. Since the algorithm is non-deterministic, the best way to test whether an implementation works properly is statistically. I would take an array of some arbitrary but small size, shuffle it a bunch of times (starting with the same permutation as input each time) and count the number of times each output permutation occurs. Then, I'd use Pearson's Chi-square Test to test this distribution for uniformity.

这篇关于为什么渔民耶茨最有用的洗牌算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！