35｜洗牌算法：随机的哲学，如何用程序来洗一副牌？

Jun 20, 2022

35｜洗牌算法：随机的哲学，如何用程序来洗一副牌？-业务开发算法50讲-极客时间



下载APP





关闭

渠道合作

推荐作者

35｜洗牌算法：随机的哲学，如何用程序来洗一副牌？

黄清昊（微扰君） · 业务开发算法50讲

课程介绍



讲述：黄清昊

时长09:20大小8.52M



你好，我是微扰君。
专栏正文已经结束了，在过去一段时间里我们一起学的知识，不知道你掌握得怎么样了呢？如果还意犹未尽的话，从今天开始我们会陆陆续续聊一些其他话题，作为特别番外，希望你可以和我一起继续享受其中的思维乐趣。
今天就先从一个颇有趣味的“洗牌算法” 来开始我们的番外之旅。
“洗牌算法”，顾名思义就是给一副牌，让你用计算机打乱这副牌，这也是一道常见的算法面试题，输入一个数组，让你将数组元素进行“一定程度”的随机重排，也就是使牌组变“乱”。
乍一看你是不是觉得这个问题也太简单了，只需要一点数学基础就能写出来。但是实际上，不同的实现，效率和正确性会有巨大的差异。
那现在就让我们一起来探究洗牌算法的不同实现方式吧。
如何洗牌首先考虑最直观的实现，就是直接模拟现实世界里人们是如何洗牌的。
生活中一种比较常见的洗牌做法就是把牌从牌堆中切出一叠，调换其在牌组中的顺序，然后重复这个过程许多次，直至牌组被打乱至不可预测的状态，我们就认为之后的发牌是具有随机性的，所以游戏可以公平的进行。
用计算机当然可以很轻松地模拟这个过程，而且相比手动一次切出一叠，用计算机我们可以更精细的每次选出两张牌直接进行位置交换，并反复进行这个过程。直觉告诉我们，经过很多次操作之后，牌就被很好的打乱了，而且因为我们是随机交换的，所以各种可能的牌组排列理论上出现的概率是差不多的。
代码写出来并不难，大概如下：
void shuffle(vector<int>& arr) {
  int n = arr.size();
  int swaps = 1000;
  for (int i = 0; i < swaps; i++) {
    int x = rand() % n;
    int y = rand() % n;
    swap(arr[x], arr[y]);
  }
}
但这个算法真的是正确的吗？
我们需要打乱多少次才能确保牌真的是乱的呢？这里我们选的交换次数是 1000 次，对于一副扑克牌来说肯定是够了，但如果只交换 5 次，显然没有办法覆盖所有可能出现的排列方式，那交换的次数到底如何取就是一个问题，这个数字显然会和牌组的大小有关。
不过，在讨论需要多少次才能真正打乱数组之前，我们首先要来明确定义一下“乱”这个词，毕竟这不是一个很严谨的数学描述，无法量化，在计算机的世界里，我们当然更青睐精确的描述。
对于洗牌算法来说，“乱”可以这样定义：随机生成数组的一种排列，使数组的所有排列情况都能以等概率的方式被选出来，并且我们的方案需要覆盖所有的排列方式。
有 n 个元素的数组，通过排列组合的知识，我们知道一共有 n! 种不同的排列方式，所以我们就需要有一个算法，让每种排列方式都以 1/n! 的概率出现，或者说，让每个位置出现各个元素的概率是 1/n，就可以覆盖所有排列且概率相同。
具体怎么操作呢？
在对 n 个不同元素进行排列时，我们可以从第一位开始枚举，等概率的选择 1～n 中的某一个，然后进行第二位的枚举，选择剩下的 n-1 个元素中的某一个……直到选取最后一个元素，这样的排列总数为 n!，因为我们是完全随机选择的，不会产生某些排列出现概率高于其他情况概率的情况。
Fisher-Yates Shuffle 算法基于这个想法，我们自然就能想到一种很直观的实现方式，Fisher-Yates Shuffle 算法。
思路就是将刚刚描述的排列过程直接翻译成代码，逐位确定数组每个位置应该选择的元素，每次选择的时候从剩余可选的元素中随机选择一个即可。
为了维护剩余的元素，我们需要用另一个数组去存储剩余元素，一开始放入所有的元素，然后每次确定一位就要将该元素从数组中移除掉。
翻译成代码如下：
void Fisher_Yates_Shuffle(vector<int>& arr,vector<int>& res) {
     int k;
     int n = arr.size();
     for (int i=0;i<n;i++) {
       k=rand()%arr.size();
       res.push_back(arr[k]);
       arr.erase(arr.begin()+k);
     }
}
其中 arr 就是我们待打乱的数组，res 则是最终打乱之后的排列结果。
但是相信你也看到了，这个算法的弊端很明显。数组的随机删除操作会带来 O(n) 的时间复杂度，所以整体的时间复杂度就是 O(n^2)，并且引入了额外的数组来存放候选集时，也引入了 O(n) 的空间复杂度。这并不是一个理想的时空复杂度。
Knuth-Durstenfeld Shuffle  算法因此，Knuth 和 Durstenfeld 在此基础上进行了改进，采用直接在原始数组上操作的方式，避免了 O(n) 的额外空间开销，也把时间复杂度降到了 O(n)。
做法和 Fisher 的本质其实是一样的，只不过在随机选择和交换的时候采取了一个小 trick，我们来看具体是怎么做的。
仍然逐位进行选择，但是当我们在选择第 i 位的时候，会假设 0～i-1 位已经确定，那么 i 的可选范围其实就是当前数组的第 i～n-1 位，于是我们只需要把第 i 位元素和第 i～n-1 位元素中的任意一个元素交换，就可以实现随机选择的效果。
翻译成代码如下：
    void shuffle(vector<int>& arr) {
        for (int i = 0; i < n; i++) {
            int tmp;
            int target = i + rand() % (n - i);
            tmp = arr[i];
            arr[i] = arr[target];
            arr[target] = tmp;
        }
    }
这样我们就可以逐个确定每一位元素的位置，等可能的从所有的可能项中选择，保证等概率性。所需的时间复杂度为 O(n)，空间复杂度为 O(1)。
看这个做法你可能还是有点疑惑，怎么严格证明这样的洗牌算法是等概率的呢？
其实我们只需要看每个位置出现各个元素的概率是不是 1/n 就可以了。这里直接引用我之前写的洗牌算法的力扣题解的证明：
先看第一个位置，由于我们是从 n 个元素中随机选择一个，每个元素出现的概率显然是 1/n。
而对于第二个位置，我们要考虑这个元素没有出现在之前的选择中，然后是从剩下 n-1 个元素中随机选择一个，所以任意一个元素出现的概率是 ((n-1)/n) * (1/(n-1)) = 1/n 。
同样，第三个位置，任意元素出现的概率应该保证前面两个位置都没有选中，那是 (n-1/n)*(n-2/n-1)*(1/n-2) = 1/n 。
依次递推，所以你会发现每个位置任意元素出现的概率都是相等的，1/n 。
这就可以严格的证明我们的算法是正确的。
那事实上，在我们日常业务开发中，这种需要随机的场景其实也是很多的。
比如知名的注册中心 Eureka，它客户端侧的负载均衡就是基于洗牌算法实现的，大致的做法就是把每个客户端维护的服务器的 IPList 打乱，然后尝试逐个请求服务器的接口，直至请求成功。
在 java.util.Collections 里也有内置的 shuffle 函数（也就是洗牌算法）用于打乱数组元素，事实上最新的 Eureka 里的随机负载均衡策略也是用 JDK 内置的 shuffle 函数实现的，感兴趣的话，你可以看具体代码。
        public static <T extends EurekaEndpoint> List<T> randomize(List<T> list) {
          List<T> randomList = new ArrayList<>(list);
          if (randomList.size() < 2) {
              return randomList;
          }
          Collections.shuffle(randomList,ThreadLocalRandom.current());
          return randomList;
      }
核心逻辑非常简单，就是简单的调用 shuffle 函数，将实现注册的 IP 列表通过 randomize 函数打乱，之后逐一请求。
总结我们今天学习了三种不同的洗牌算法思路：每次随机选出两张牌交换，然后不断重复这一过程、Fisher-Yates Shuffle 算法、Knuth-Durstenfield 算法。
第一种是源于日常生活中的观察，但是它不能说是正确的洗牌算法，根本原因是因为对问题没有清晰的定义，比如对于打乱的结果“乱”到底如何量化？这个问题不解决，我们就没法确定自己的算法是否是正确的。
而我们在解决计算机问题的时候，很多时候是需要去寻求本质解的。后两种思路，在找到了精确的定义之后，就可以让算法能保证数组每种排列出现的概率是等可能的了。
Knuth-Durstenfield 算法是对 Fisher-Yates 算法的一种优化。在日常开发中，我们也需要分析每个可能产生性能开销的地方，然后尝试是否有优化的可能，这个时候可能需要一些 tricks，除了灵光一现，也需要一些经验。不断学习各种算法就是一种非常好的积累经验的方法。
课后思考如果别人提供了一个洗牌算法的实现，你有没有什么办法可以大致验证这个算法的正确性呢？
欢迎在留言区留下你的思考，和我一起讨论。如果觉得这篇文章对你有帮助，也欢迎转发给你的朋友或者同事一起学习。

洗牌算法是计算机科学中的重要话题，本文介绍了洗牌算法的基本概念和不同的实现方式。文章首先探讨了洗牌算法的背景和意义，详细讨论了不同的洗牌算法实现方式，包括最直观的方法、Fisher-Yates Shuffle算法和Knuth-Durstenfeld Shuffle算法。通过对比不同算法的时间复杂度和空间复杂度，文章指出了Knuth-Durstenfeld Shuffle算法的优势，并给出了该算法的具体实现代码。此外，文章还提到了洗牌算法在实际应用中的例子，如Eureka注册中心的负载均衡和Java中的Collections.shuffle函数。总的来说，本文通过深入浅出的方式介绍了洗牌算法的原理和实际应用，对读者了解和掌握洗牌算法具有一定的参考价值。文章还探讨了三种不同的洗牌算法思路，并提出了课后思考问题，引发读者对算法正确性的思考和讨论。文章内容丰富，既有理论知识又有实际应用，适合对洗牌算法感兴趣的读者阅读学习。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

2022-06-20

赞 1

提建议

即学即练｜工程实战篇：复习卡一键直达

36｜分布式事务：如何理解两阶段提交？

 写留言

精选留言

由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。

