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 的主要素材,上面的解释非常详细

转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn

发表评论

电子邮件地址不会被公开。 必填项已用*标注