Fisher–Yates shuffle 算法 – To Be Hacker-演道网

导言

Fisher–Yates shuffle 是一个将序列打乱的“洗牌”算法。由 Ronald Fisher 与 Frank Yates 在 《Statistical tables for biological, agricultural and medical research》一书中最先提出，因此得名。

其后 Donald Knuth 在《The Art of Computer Programming》一书中将其推广开来，故又称之为 Knuth shuffle 。

算法思想

Fisher and Yates 最初的方法

FISHER 与 YATES 最初提出这个算法时，计算机尚没有普及，所以说这是一种在纸笔上操作的算法。除此之外，你还需要一个随机数表用以提供随机性。

算法的执行过程如下：

1. 将序列写成一行，并赋予下标 1 到 N
2. 生成一个 1 到现有序列长度之间的随机数 K
3. 从左往右，将序列中第 K 个数拿出来追加到一个新的序列中
4. 重复2、3步，直至所有的数都已被拿入新序列
5. 这个新序列即为一组原序列的随机排列

当今的算法

Fisher与 Yates 最初的算法适合纸笔操作，但对计算机而言并不友好。为此 Richard Durstenfeld 在 1964 年针对于计算机对其作出了一些改进：

1. 将序列 lst 标上下标，从 0 到 n-1
2. 设一变量 i 等于 n-1
3. 生成一个 0 到 i 的随机数 r ，将 lst[r] 与 lst[i] 交换
4. i 自减 1
5. 重复 2-4 步，直至 i 等于 0
6. 序列 lst 即为一组原序列的随机排列

（这里 i 是从 n-1 到 0 的。类似的，i 从 0 到 n-1 也是可以的，这里就不再累述了。）

算法改变的并不多，但影响却是巨大的。他将一个时间复杂度为 O(n^2) 的算法优化为了一个 O(n) 的算法。其关键在于原算法的第三步消耗了很多无用的计算在数数上。

示例

Wikipedia 上有两份详细的示例，点击这里。

实现

了解算法思想后实现非常简单，下面是一份 Python 3 的实现：

参考：

Wikipedia：本篇 Post 的主要素材，上面的解释非常详细