侧边栏壁纸
  • 累计撰写 6 篇文章
  • 累计创建 6 个标签
  • 累计收到 0 条评论
标签搜索

算法之美1:Knuth洗牌算法 Knuth-Shuffle

jackknife007
2022-03-17 / 0 评论 / 0 点赞 / 398 阅读 / 2,341 字
温馨提示:
本文最后更新于 2022-03-17,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

前言

今天开启一个全新的系列,算法之美。旨在介绍和总结让人眼前亿亮、回味无穷、并值得全文背诵的经典或有趣的算法。

我一直相信算法中蕴含的思想和看待问题的方法,无论对什么领域都能有所启发。就像我的本专业数学,即使目前从事的工作和数学相去甚远,但数学给我带来的思维训练足够使我受益终身了。

本系列也是在督促自己不断学习,少打王者荣耀。希望能够保持周更。

Knuth-Shuffle

作为本系列的开篇,这个算法绝对能够镇得住场子。这个算法就是大名鼎鼎的 Knuth-Shuffle,即Knuth洗牌算法。

在生活中,一定能够遇到需要打乱一组数据的场景,比如最简单的洗牌、扫雷中地雷的随机排列。再推广下去,抽签也能算作其中的一种场景。这些场景都有两个关键词:随机、等概率。

随机指的是每个场景的结果都需要是随机的,谁也不知道结果是哪一种排列。

等概率是指每种结果出现的概率都应该相同。即每种结果都是公平的。

洗牌需要相对洗的很乱、抽签需要确保每个人抽中签的概率都一样。。。。

对于一道概率相关的题,暴力枚举法肯定是最容易想到的。既然需要等概率的返回一种结果,那么只需要先计算出每一个可能的结果,再随机的返回一个就好了。

比如有n个数{1, 2, ..., n},随机的排列一共有n!种情况,那么取其中一个的时间复杂度就是O(n!),这显然是我们无法接受的。那有没有时间复杂度低的算法呢。

首先我们来看抽签的概率。

对于抽签我们都很熟悉,无论你先抽后抽,抽中的概率都是相同的。下面先做一个简单的计算。

假设有n个人,另有n个纸团,其中一个写了字,剩下的n-1的纸团没有字。

那我如果第一个抽,从n个纸团中抽一个纸团,显然抽中的概率是:

$$\frac{1}{n}$$

如果我第二个抽,抽中的概率是

$$P = \frac{n-1}{n} \times \frac{1}{n-1} = \frac{1}{n}$$

因为如果我第二个抽并且抽中了,那么第一个人一定没有抽中。

以此类推,不论我第几个抽签,抽中的概率都相同。

看完了抽签,再回到洗牌算法。公平洗牌需要每种打乱的情况的概率是相同的。对于每张特定的牌的角度看,需要使得这张牌出现在所有位置的概率都相同。是不是很像抽签问题,即对于某一个签,其在所有位置被抽中的概率相同。

所以类似抽签算法,在洗牌算法中,第一步,我们先从n张牌中抽一张,放在一边。第二步,再从剩下的n-1张中抽一张,也放在另一堆。这样操作n步,就得到了一副洗好的牌。

各大语言中使用random中的shuffle也是使用了这种算法。

可以看到,Python中的random.shuffle源码如下

    def shuffle(self, x, random=None):
       """Shuffle list x in place, and return None.

       Optional argument random is a 0-argument function >returning a
       random float in [0.0, 1.0); if it is the default None, >the
       standard random.random will be used.

       """

       if random is None:
           randbelow = self._randbelow
           for i in reversed(range(1, len(x))):
               # pick an element in x[:i+1] with which to >exchange x[i]
               j = randbelow(i+1)
               x[i], x[j] = x[j], x[i]
       else:
           _int = int
           for i in reversed(range(1, len(x))):
               # pick an element in x[:i+1] with which to >exchange x[i]
               j = _int(random() * (i+1))
               x[i], x[j] = x[j], x[i]

Java中Collections.shuffle

   public static void shuffle(List<?> list) {
       Random rnd = r;
       if (rnd == null)
           r = rnd = new Random(); // harmless race.
       shuffle(list, rnd);
   }
   @SuppressWarnings({"rawtypes", "unchecked"})
   public static void shuffle(List<?> list, Random rnd) {
       int size = list.size();
       if (size < SHUFFLE_THRESHOLD || list instanceof >RandomAccess) {
           for (int i=size; i>1; i--)
               swap(list, i-1, rnd.nextInt(i));
       } else {
           Object arr[] = list.toArray();

           // Shuffle array
           for (int i=size; i>1; i--)
               swap(arr, i-1, rnd.nextInt(i));

           // Dump array back into list
           // instead of using a raw type here, it's possible >to capture
           // the wildcard but it will require a call to a >supplementary
           // private method
           ListIterator it = list.listIterator();
           for (int i=0; i<arr.length; i++) {
               it.next();
               it.set(arr[i]);
           }
       }
0

评论区