Fisher–Yates shuffle 洗牌算法

洗牌算法又名「Fisher–Yates shuffle」不难看出是以人名命名

将原有的有限集合打乱(就像洗扑克牌一样),生成随机排序的集合

原始版本是 1938 年的 Ronald Fisher 和 Frank Yates 写的

《Statistical tables for biological, agricultural and medical research》书中给出的算法描述

1964 年由 Richard Durstenfeld 改编为适用于电脑编程的版本

通俗地说:

将 n 个数集中 n 位置上的数与 n - 1 个随机位置的数交换

n - 1 上的数与 n - 2 个随机位置上的数交换

以此类推

一图胜千言:

Fisher–Yates shuffle 图解

点击这里查看动画演示, 请 PC 上食用 (opens new window)

# 使用场景

因其主要用于数据集合打乱

所以多用于随机的场景

比如 1000 道数学题随机出题

比如「扫雷」游戏,随机数量的雷区

# 多版本对比

「FY」(洗牌算法)原理相当简单

就是遍历整个数组,从数组的最前面或最后面取值

与数组的剩余随机项的值进行交换

最终实现了数组的乱序

# lodash 版本

「lodash」是前端开发常用的工具类库

里面有关于「FY」的实现

function shuffle(array) {
  const length = array == null ? 0 : array.length
  if (!length) {
    return []
  }
  let index = -1 // 待交换索引位,从数组第 0 项开始
  const lastIndex = length - 1
  const result = copyArray(array)
  while (++index < length) {
    // 随机索引位,将[0, length - 1] 中区间中取出随机整数
    const rand = index + Math.floor(Math.random() * (lastIndex - index + 1))
    // 取出随机索引位值,此时随机索引位就空出来了
    const value = result[rand]
    // 使用待交换索引位值填充空出来的随机索引位
    result[rand] = result[index]
    // 将之前取出的随机索引位值赋值给待交换索引位
    result[index] = value
  }
  return result
}

export default shuffle
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

lodash 中 shuffle 源码 (opens new window)

关键点如下:

  • lodash 版本多了关于边界的异常处理,比如数组长度为 0 时不进行直接返回

  • 从数组起始 0 位置索引开始交换

  • 遍历的次数是数组的长度 - 1

  • 随机索引位与待交换索引位可能重复,比如 index 与 rand 值都可能为 1

# phaser3 版本

「phaser3」 是一款游戏开发引擎,其工具类对象中也有关于此的实现

var Shuffle = function (array)
{
  // 缺少 i = 0 时的交换
    for (var i = array.length - 1; i > 0; i--)
    {
        var j = Math.floor(Math.random() * (i + 1));
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    return array;
};

module.exports = Shuffle;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

phash3 中 shuffle 源码 (opens new window)

关键点如下:

  • 从数组最大索引位置开始交换

  • 无异常处理

  • 遍历次数为 数组长度 - 2 次,缺少一次遍历,最后一次遍历数组只有一项,随机索引与待交换索引相同,交换无意义,结果不影响

  • 随机索引位与待交换索引位可能重复

# leetcode 版本

扰乱数组 (opens new window)算法题出现的

看了下 javascript 实现版本

对比之前的,原理大致相同

只是多了数组复位功能

有兴趣自行查看

# 扩展 Array 方法

通常是不建议扩展原生对象的

避免将来出现与官方实现冲突的问题

看下扩展实现

Array.prototype.shuffle = function() {
  // 当 [1, 2, 3, 4].shuffle() 调用时
  // this = [1, 2, 3, 4]
  let input = this
  for (let i = input.length - 1; i >= 0; i --) {
    let rand = Math.floor(Math.random() * (i + 1))
    let valAtRand = input[rand]
    input[rand] = input[i]
    input[i] = valAtRand
  }
  return input
}

// 使用
let arr = [1, 2, 3, 4]
arr.shuffle() // [4, 1, 2, 3],结果是随机的,所以看到的与此不一致正常
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 小结

通过 「Fisher–Yates shuffle」洗牌算法背景交代了基础的原理

通常多个项目版本的对比

明确了不同的实现方式及对应的关键点

最后通过 Array 原型扩展实现了方法的自定义

扫一扫,微信中打开

微信二维码