algorithm - 随机打乱数组

Question

查看以下用于洗牌数组的算法：

def shuffleSort(a):
  N = len(a)
  for i in range(N):
    j = random.randint(0, i)
    a[j], a[i] = a[i], a[j]

我相信它被称为Fisher-Yates算法？我正在寻找一个严格的数学证明来证明这为什么有效。更具体地说，让(a1, ..., an)是 的一个排列n，我想证明p((x1 = a1, ..., xn = an)) = 1/n!。

标签： algorithmshuffle

Answer 1

这是一个典型的归纳证明。

归纳假设是，对于 k ∈ {0, 1, ..., n}，对于 {0, 1, ..., k − 1} 的每个排列 π，概率至少为 1/k!，列表值为 a(π(0)), a(π(1)), ..., a(π(k−1)), a(k), a(k+1), ..., a( n-1)，其中 a(i) 表示位置 i 处的原始值。对于 k = n，这证明了每个排列的概率至少为 1/n！，这几乎就是我们想要的；剩下的就是通过观察这些事件是不相交的并且概率总和为一，因此平等必须在任何地方都成立。

基本情况 k = 0 是显而易见的；只有一个排列，它以 1/0 的概率存在于原始列表中！= 1 假设。

对于归纳步​​骤，令 φ = (π(k) k) ∘ π，用英语表示，通过将 k 交换回其原始位置来修改 π 的排列。调用归纳假设，在 k-1 步之后 φ 存在于列表中的概率至少为 1/(k-1)!。概率至少为 1/k 时，随机数为 π(k)，它以至少 1/(k-1) 的概率将所需的排列放入列表中！× 1/k = 1/k!。