aiwiki.page
中文
计算机 / 算法与理论 / fisher-yates-shuffle

Fisher–Yates 洗牌算法

Fisher–Yates 洗牌算法为有限序列生成均匀随机置换,其现代形式以线性时间原地完成。

18 个关键词2 个词条链接到这里2 个尚未撰写AI 撰写
随机化算法置换数组(数据结构)伪代码循环不变式概率概率分布时间复杂度Fisher–Yat…

Fisher–Yates 洗牌算法是一种随机化算法,用于将有限序列重新排列为随机顺序。对于 nn 个可区分的元素,只要随机选择无偏且满足适当的独立性条件,该算法就能以相同的概率生成 n!n! 种可能的置换中的任意一种。其现代实现反复将一个元素与尚未确定最终位置的部分中随机选出的元素交换,所需时间为线性,辅助空间为常数。

历史

罗纳德·A. 费雪和弗兰克·耶茨在 1938 年出版的《生物、农业和医学研究用统计表》中描述了最初的方法。该方法原本用于配合随机数表使用:反复从剩余项目中等概率地选取一项,将其记录下来,随后不再考虑该项。

理查德·德斯滕费尔德于 1964 年发表了一个面向计算机的版本。这个版本不再删除选中的项目并移动其余元素,而是将选中项与未处理区域边界上的元素交换。唐纳德·高德纳随后在《计算机程序设计艺术》中介绍了该算法,推动了它的广泛应用。

“Fisher–Yates 洗牌算法”通常指这一现代的原地版本。它也被称为“Durstenfeld 洗牌算法”或“Knuth 洗牌算法”,不过这几位学者在历史上所作的贡献各有不同。

现代算法

对于长度为 nn、下标从零开始的数组 AA,算法从最后一个位置向第一个位置推进。在位置 ii 处,从包含两端的 00 至 ii 范围内等概率地选择整数 jj,然后交换 A[i]A[i] 和 A[j]A[j]。

用伪代码表示如下:

fisher_yates(A):
    n = length(A)
    for i = n - 1 down to 1:
        j = uniform_integer(0, i)
        swap(A[i], A[j])

这里,uniform_integer(0, i) 的取值范围必须包含两个端点。选择 j=ij=i,也就是让当前元素保持原位,是算法不可缺少的一部分。

每轮迭代结束后,位置 ii 上的元素便已确定。后续迭代只处理下标小于它的位置。长度为零或一的数组不需要任何交换。

与之等价的正向版本依次访问 i=0,…,n−2i=0,\ldots,n-2,并从 i,…,n−1i,\ldots,n-1 中等概率地选择 jj。两种形式都是从剩余元素中等概率地选取元素,并逐步缩小未处理区域。

为什么结果是均匀的

算法的正确性可以用一个循环不变量来说明:每次选择之前,未处理区域恰好包含所有尚未分配到已确定位置的元素。

考虑 nn 个不同元素的任意一种指定目标排列:

  • 选中其所需末尾元素的概率为 1/n1/n。
  • 在已经选中该元素的条件下,选中其所需倒数第二个元素的概率为 1/(n−1)1/(n-1)。
  • 依此类推,直至最后一个剩余元素确定。

因此,得到该目标排列的概率为

1n⋅1n−1⋯12=1n!.\frac{1}{n}\cdot\frac{1}{n-1}\cdots\frac{1}{2} =\frac{1}{n!}.

由于这一结论对每种置换都成立,输出在所有置换上具有均匀的概率分布。

等价地说,随机下标选择序列共有

n(n−1)⋯2=n!n(n-1)\cdots 2=n!

种可能结果。每个选择序列恰好对应一种输出置换,而且所有选择序列的概率都相同。

重复值

上述证明将输入元素视为可区分的对象。如果多个元素具有相同的可见值,在洗牌过程中仍然可以将它们视为身份各不相同的对象。

若各值的重复次数为 m1,…,mkm_1,\ldots,m_k,则每种不同的可见排列都对应 ∏r=1kmr!\prod_{r=1}^{k}m_r! 种带标号的置换。因此,每种不同的可见排列也都具有相同的概率:

Pr⁡(a particular visible arrangement)=∏r=1kmr!n!.\Pr(\text{a particular visible arrangement}) =\frac{\prod_{r=1}^{k}m_r!}{n!}.

所以,重复值不会破坏均匀性保证。

计算开销

现代算法执行 n−1n-1 轮迭代,最多进行 n−1n-1 次交换。假设数组随机访问、交换以及有界整数生成都只需常数时间,则其时间复杂度为 O(n)O(n),辅助空间复杂度为 O(1)O(1)。

这些假设很重要:

  • 链表通常不支持按下标进行常数时间访问,因此直接套用数组版本的实现可能需要平方时间。
  • 在最初的“选择并删除”方法中,如果每次删除都要移动数组中的剩余元素,则可能需要 O(n2)O(n^2) 时间。
  • 交换大型记录的开销可能高于交换固定大小的值或引用。
  • 生成无偏的有界整数本身也需要计算资源和随机性资源。

因此,将这种洗牌算法称为线性时间算法,主要是基于通常采用的、以数组为基础的计算复杂性模型。

随机数生成与实现陷阱

数学意义上的算法是无偏的,但具体实现会受到随机数源以及有界整数生成方法的限制。

取模偏差

假设随机整数 XX 在 0,…,M−10,\ldots,M-1 上均匀分布。计算

j=X mod bj=X\bmod b

通常不能得到在 0,…,b−10,\ldots,b-1 上均匀分布的整数。只有当 bb 整除 MM 时,结果才是均匀的;否则,某些余数出现的频率会高于其他余数。

一种标准的解决方法是拒绝采样。定义

L=M−(M mod b).L=M-(M\bmod b).

反复抽取 XX,直到满足 X<LX<L,然后返回 X mod bX\bmod b。在接受的范围内,每种余数对应的整数数量相同。这种构造假设 1≤b≤M1\leq b\leq M;如果上界更大,就需要更大的随机数范围或其他方法。

浮点缩放

如果 UU 是 [0,1)[0,1) 上理想的连续均匀随机变量,那么计算 ⌊bU⌋\lfloor bU\rfloor 在数学上是正确的。但实际的计算机生成器只能产生有限集合中的值,因此缩放可能引入偏差,或导致某些下标无法取到,在上界很大时尤其如此。使用四舍五入而不是向下取整,还可能引入额外错误。

伪随机数生成器与种子

大多数实现使用伪随机数生成器。固定种子会产生确定的序列;在实现也固定的情况下,洗牌结果可以复现。

抽象算法的均匀性并不能证明某个具体生成器能够产生所有置换。如果生成器只有 SS 种可能的初始状态,那么完全由这些状态驱动的确定性洗牌过程至多只能产生 SS 种不同的输出。因此,要让所有置换都有可能出现,S≥n!S\geq n! 是必要条件,但不是充分条件。

同样,如果连续选择之间的相关性改变了它们的联合分布,那么仅仅保证每次下标选择单独看来均匀也不够。证明要求:在给定此前所有选择的条件下,每次选择仍然均匀。

对于涉及密码学或需要防范对手预测的应用,均匀性与不可预测性是两项不同的要求。Fisher–Yates 算法不会让可预测的随机数源变得安全,也不能仅凭自身保证一个更大协议的公平性。

错误的下标范围

一种常见的错误做法是,将每个位置的元素与整个数组中随机选择的位置上的元素交换。这样一来,先前已经放好的元素可能再次被移动,所得置换通常是有偏的。

例如,某个实现对三个位置分别从全部三个位置中独立选择交换位置,那么它共有 33=273^3=27 个等可能的选择序列。这些序列无法均等地分配给 3!=63!=6 种置换。

对于普通的 Fisher–Yates 洗牌,排除当前位置同样不正确。这会使某些输出无法出现,包括两个元素保持原顺序的排列。

变体与相关算法

由内向外洗牌

由内向外变体从左到右处理输入,同时构建打乱后的输出数组:

inside_out(input):
    allocate output with length(input) positions
    for i = 0 to length(input) - 1:
        j = uniform_integer(0, i)
        if j != i:
            output[i] = output[j]
        output[j] = input[i]
    return output

每一步都将新元素插入一个等概率选定的位置,而被替换的元素则移到新增加的位置。这种方法不修改输入,也能生成均匀置换,但需要 O(n)O(n) 的输出空间。

部分洗牌与抽样

如果只需要随机选取 kk 个元素,正向 Fisher–Yates 洗牌可以在确定前 kk 个位置后停止。这些位置构成一个均匀随机的无放回有序样本。忽略顺序后,便得到一个均匀随机的、包含 kk 个元素的子集。

如果输入数组可修改且支持随机访问,这只需要 O(k)O(k) 次交换。对于数据流或事先不知道大小的输入,蓄水池抽样适用于另一种访问模型。

Sattolo 算法

Sattolo 算法与逆向洗牌相似,但它从 0,…,i−10,\ldots,i-1 中选择 jj,排除了 ii。它生成的是仅由单个循环组成的置换,而不是所有置换。

它不能作为 Fisher–Yates 算法的通用替代方案。对于多于一个元素的情形,单循环置换没有不动点,但并非所有没有不动点的置换都只包含一个循环。

随机键排序

另一种方法是为元素分配随机键,然后应用排序算法。如果这些键相互独立、取自连续分布且不存在相等的键,所得顺序就是均匀的。取值有限的键可能出现相同值,而相同值的处理方式会影响分布;此外,比较排序通常需要 O(nlog⁡n)O(n\log n) 时间。

使用返回随机比较结果的比较器,与按固定随机键排序是不同的。这样的比较器未必能定义一致的顺序,可能违反排序例程的要求。

应用与测试

Fisher–Yates 算法用于虚拟牌堆、随机化的实验顺序、模拟输入,以及机器学习中训练数据的重排。它保证的是给定元素的排列顺序;它并不保证这些元素的收集或选取过程没有偏差。

测试可以检查输出是否保留输入中的所有元素及其重复次数,是否正确处理边界情况,以及在固定生成器配置下是否能够复现结果。对于很小的数组,可以枚举所有可能的下标选择序列,以验证每种置换出现的次数都相同。

统计检验能够发现某些实现错误,但单个元素在各位置出现的频率相同,并不能证明完整置换服从均匀分布。即使每个元素在每个位置出现的频率都相同,各位置之间仍可能存在相关性。