• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

随机打乱数组及Fisher–Yates shuffle算法详解

互联网 diligentman 5天前 5次浏览

介绍几种随机打乱数组的方法,及其利弊。

一、Array.prototype.sort 排序

注意一下,sort() 方法会改变原数组,看代码:

// ES6 写法
function randomShuffle(arr) {
  return arr.sort(() => Math.random() - 0.5)
}

// ES5 写法
function randomShuffle(arr) {
  var compareFn = function () {
    return Math.random() - 0.5
  }
  return arr.sort(compareFn)
}

但实际上这种方法并不能真正的随机打乱数组。在多次执行后,每个元素有很大几率还在它原来的位置附近出现。可看下这篇文章:常用的 sort 打乱数组方法真的有用?

二、Fisher–Yates shuffle 经典洗牌算法

这种算法思想,目前有两种稍有不同的实现方式,这里我把它们都算入 Fisher–Yates shuffle。分别是 Fisher–Yates shuffleKnuth-Durstenfeld Shuffle

著名的 Lodash 库的方法 _.shuffle() 也是使用了该算法。

1. Fisher–Yates shuffle(Fisher and Yates’ original method)

由 Ronald Fisher 和 Frank Yates 提出的 Fisher–Yates shuffle 算法思想,通俗来说是这样的:

假设有一个长度为 N 的数组

  1. 从第 1 个到剩余的未删除项(包含)之间选择一个随机数 k。
  2. 从剩余的元素中将第 k 个元素删除并取出,放到新数组中。
  3. 重复第 1、2 步直到所有元素都被删除。
  4. 最终将新数组返回

实现

function shuffle(arr) {
  var random
  var newArr = []

  while (arr.length) {
    random = Math.floor(Math.random() * arr.length)
    newArr.push(arr[random])
    arr.splice(random, 1)
  }

  return newArr
}

举例

假设我们有 1 ~ 8 的数字

表格每列分别表示:范围、随机数(被移除数的位置)、剩余未删除的数、已随机排列的数。

Range Roll Scratch Result
  1 2 3 4 5 6 7 8  

现在,我们从 1 ~ 8 中随机选择一个数,得到随机数 k 为 3,然后在 Scratch 上删除第 k 个数字(即数字 3),并将其放到 Result 中:

Range Roll Scratch Result
1 – 8  3 1 2 3 4 5 6 7 8 3 

现在我们从 1 ~ 7 选择第二个随机数 k 为 4,然后在 Scratch 上删除第 k 个数字(即数字 5),并将其放到 Result 中:

Range Roll Scratch Result
1 – 7  4 1 2 3 4 5 6 7 8 3 5 

现在我们从 1 ~ 6 选择下一个随机数,然后从 1 ~ 5 选择依此类推,总是重复上述过程:

Range Roll Scratch Result
1–6 5 1 2 3 4 5 6 7 8 3 5 7
1–5 3 1 2 3 4 5 6 7 8 3 5 7 4
1–4 4 1 2 3 4 5 6 7 8 3 5 7 4 8
1–3 1 1 2 3 4 5 6 7 8 3 5 7 4 8 1
1–2 2 1 2 3 4 5 6 7 8 3 5 7 4 8 1 6
    1 2 3 4 5 6 7 8 3 5 7 4 8 1 6 2
2. Knuth-Durstenfeld Shuffle(The modern algorithm)

Richard Durstenfeld 于 1964 年推出了现代版本的 Fisher–Yates shuffle,并由 Donald E. Knuth 在 The Art of Computer Programming 以 “Algorithm P (Shuffling)” 进行了推广。Durstenfeld 所描述的算法与 Fisher 和 Yates 所给出的算法有很小的差异,但意义重大。

-- To shuffle an array a of n elements (indices 0..n-1):  
for i from n−1 downto 1 do  // 数组从 n-1 到 0 循环执行 n 次
  j ← random integer such that 0 ≤ j ≤ i  // 生成一个 0 到 n-1 之间的随机索引
  exchange a[j] and a[i] // 将交换之后剩余的序列中最后一个元素与随机选取的元素交换

Durstenfeld 的解决方案是将“删除”的数字移至数组末尾,即将每个被删除数字与最后一个未删除的数字进行交换

实现

// ES6 写法
function shuffle(arr) {
  let i = arr.length

  while (--i) {
    let j = Math.floor(Math.random() * i)
    ;[arr[j], arr[i]] = [arr[i], arr[j]]
  }

  return arr
}


// ES5 写法
function shuffle(arr) {
  var i = arr.length
  var j
  var t

  while (--i) {
    j = Math.floor(Math.random() * i)
    t = arr[i]
    arr[i] = arr[j]
    arr[j] = t
  }
  
  return arr
}

Knuth-Durstenfeld Shuffle 将算法的时间复杂度降低到 O(n),而 Fisher–Yates shuffle 的时间复杂度为 O(n2)。后者在计算机实现过程中,将花费不必要的时间来计算每次剩余的数字(可以理解成数组长度)。

举例

同样,假设我们有 1 ~ 8 的数字

表格每列分别表示:范围、当前随机数(即随机交互的位置)、剩余未交换的数、已随机排列的数。

Range Roll Scratch Result
  1 2 3 4 5 6 7 8  

我们从 1 ~ 8 中随机选择一个数,得到随机数 k 为 6,然后交换 Scratch 中的第 6 和第 8 个数字:

Range Roll Scratch Result
1 – 8  6 1 2 3 4 5 8 7 6 

接着,从 1 ~ 7 中随机选择一个数,得到随机数 k 为 2,然后交换 Scratch 中的第 2 和第 7 个数字:

Range Roll Scratch Result
1 – 7  6 1 7 3 4 5 8 2

继续,下一个随机数是1 ~ 6,得到的随机数恰好是 6,这意味着我们将列表中的第 6 个数字保留下来(经过上面的交换,现在是 8),然后移到下一个步。同样,我们以相同的方式进行操作,直到完成排列:

Range Roll Scratch Result
1 – 6  6 1 7 3 4 5 8 2 6 
1 – 5  1 5 7 3 4 1 8 2 6 
1 – 4  3 5 7 4 3 1 8 2 6 
1 – 3  3 5 7 4 3 1 8 2 6 
1 – 2  1 7 5 4 3 1 8 2 6 

因此,结果是 7 5 4 3 1 8 2 6

三、总结

若要实现随机打乱数组的需求,不要再使用 arr.sort(() => Math.random() - 0.5) 这种方法了。目前用得较多的是 Knuth-Durstenfeld Shuffle 算法。

四、参考

  • 常用的 sort 打乱数组方法真的有用?
  • Fisher–Yates Shuffle 可视化
  • Fisher–Yates shuffle wiki
  • 洗牌算法(shuffle)的 js 实现

程序员灯塔
转载请注明原文链接:随机打乱数组及Fisher–Yates shuffle算法详解
喜欢 (0)