avatar

阿炳的小站

谁知难过 分一丁目赠我

  • 首页
  • 关于
  • 友链
Home Shuffling 的算法艺术
文章

Shuffling 的算法艺术

Posted 昨天 Updated 昨天
By abing
8~11 min read

牌类游戏,自古到今都有各种变型,从三国杀、炉石到斗地主以及更久远的德州,这些卡牌游戏永远都绕不开一个问题——洗牌。而洗牌的本质,就是让牌的每个排列出现的概率相等。我们现实中要实现基础的随机化洗牌自然容易,当然,魔术师也会使用各种方法,来诱导你相信,他们的洗牌是 “公平” 的。那么对于计算机来说,我们如何保证各类棋牌游戏中,洗牌的公平与随机呢?这就是今天要阐述的课题。

公平的数学基础

刚刚我们提到了洗牌如果需要公平,那就得让牌的每个排列出现的概率相等,换句话说,每个排列都得 “可能” 出现相同的次数,这就是我们所说的 “期望” 。举个例子,当我们手上有 「9、10、J」 三张牌的时候,我们可能的组合,就有如下几种:

  • 「9、10、J」,「9、J、10」

  • 「10、9、J」,「10、J、9」

  • 「J、10、9」,「J、9、10」

换个理解的方式,我们第一个位置可以有 「3」张卡牌可以选择,但是选择其一,第二次的时候,我们便只有「2」张卡牌可以供选择了,到最后,只剩下「1」张卡牌能够选择,因此总的排列数量就是「3 ✖️ 2 ✖️ 1」一共「6」种。换成4张牌的时候,我们同样可以根据这个方法算出一共有「24」种排列。

而我们的目的,就是让这每种排列出现的概率相等。

朴素的洗牌

按照我们上述朴素的想法,我们可以很快的写出对应的代码:

function originalFisherYates(arr) {
  const result = [];
  const src = arr.slice();

  while (src.length > 0) {
    const idx = Math.floor(Math.random() * src.length);
    result.push(src.splice(idx, 1)[0]);
  }

  return result;
}

上述代码在概率学上,确实做到了各种排列出现的概率一致,但是对于计算机来说——它太慢了,注意到src.splice(idx, 1) 这个,从原数组中踢出所随机出来的这个元素,其实时间复杂度是O(n) 的,而我们又要遍历整个原数组一遍,因此对于整体而言,它的时间复杂度,实际上是O(N^2) 。对于动辄几百上千的数据来说,这个时间复杂度,是我们没办法承受的,因此,我们必须要做出改进。

改进后的 Fisher-Yates

到了 1964 年,Durstenfeld 对它进行了原地优化(即就地打乱,无需新数组):

function fisherYates(arr) {
  const result = arr.slice();

  for (let i = result.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1)); // 0 <= j <= i
    [result[i], result[j]] = [result[j], result[i]];
  }

  return result;
}

上述的代码中,我们倒叙遍历数组,每次从[0, i] 中选出一个,与当前位置交换。

但是比较绕的是,为什么就地打乱,也可以做到同样的效果呢?他在数学上是正确的?那就让我们来证明一下。

第一步,当 i = n - 1 的情况下:

  • 从下标 j ∈ [0, n − 1] 中随机选一个,交换到末尾;

  • 被选中放到最后一个位置的元素有 1 / n 的概率

第二步,当 i = n - 2 的情况下:

  • 从剩下的前 n − 1 个元素中随机选一个,放到倒数第二个位置;

  • 被选中元素的概率为 1 / n - 1;

  • 所以前两步组合起来,每个元素排在某个位置的联合概率是 1 / (n - 1) * 1 / n

……

第 k 步,当 i = n - k 当情况下:

  • 从 n − k + 1 个还未“固定”的元素中,等概率选一个放在第 n − k 个位置;

  • 概率是 ​1 / n - k + 1。

……

所以到最后,我们只剩下一张牌可以选择,因此,所有的步骤组合起来,每个元素排在某个位置的联合概率(即某个组合出现的概率)为:

这样子一来,我们在数学上也证明了其正确性。

总结

Fisher-Yates 在改进后,现代 Fisher–Yates 洗牌算法在每一步中都以等概率做选择,且每一步选择独立,最终能等概率地产生所有 n! 个排列。

License:  CC BY 4.0
Share

Further Reading

OLDER

鸟群算法 Boids

NEWER

Recently Updated

  • Shuffling 的算法艺术
  • 鸟群算法 Boids
  • 远行与归乡
  • 行动力与风口、供应链、营销
  • 【数据结构】顺序表 Sequential List

Trending Tags

笔记 共赏 实习心得 docker使用技巧 随想沉思 工具技巧 C# 数据结构 git使用技巧

Contents

©2025 阿炳的小站. Some rights reserved.

Using the Halo theme Chirpy