如何公平的洗牌

编程 / 2019-07-17

洗牌,显然是一个随机算法了。随机算法还不简单?随机呗。把所有牌放到一个数组中,每次取两张牌交换位置,随机 k 次即可。

如果你的答案是这样,通常面试官会进一步问一下,k 应该取多少?100?1000?10000?

很显然,取一个固定的值不合理。如果数组中有 1000000 个元素,随机 100 次太少;如果数组中只有 10 个元素,随机 10000 次又太多。一个合理的选择是,随机次数和数组中元素大小相关。比如数组有多少个元素,我们就随机多少次。

这个答案已经好很多了。但其实,连这个问题的本质都没有触及到。此时,面试官一定会狡黠地一笑:这个算法公平吗?

我们再看问题:设计一个公平的洗牌算法。

如何公平洗牌

思路一

洗牌的结果是所有元素的一个排列。一副牌如果有 n 个元素,最终排列的可能性一共有 n! 个。公平的洗牌算法,应该能等概率地给出这 n! 个结果中的任意一个。

如思考虑到这一点,我们就能设计出一个简单的暴力算法了:对于 n 个元素,生成所有的 n! 个排列,然后,随机抽一个。

这个算法绝对是公平的。但问题是,复杂度太高。复杂度是多少呢?O (n!)。因为,n 个元素一共有 n! 种排列,我们求出所有 n! 种排列,至少需要 n! 的时间。

思路二

我们再换一个角度思考 “公平” 这个话题。其实,我们也可以认为,公平是指,对于生成的排列,每一个元素都能独立等概率地出现在每一个位置。或者反过来,每一个位置都能独立等概率地放置每个元素。

基于这个定义,我们就可以给出一个简单的算法了。说这个算法简单,是因为他的逻辑太容易了,就一个循环:

for(int i = n - 1; i >= 0 ; i -- )
    swap(arr[i], arr[rand(0, i)]) // rand(0, i) 生成 [0, i] 之间的随机整数

这么简单的一个算法,对于生成的排列,每一个元素都能独立等概率的出现在每一个位置。或者反过来,每一个位置都能独立等概率的放置每个元素。

i 从后向前,每次随机一个 [0…i] 之间的下标,然后将 arr [i] 和这个随机的下标元素,也就是 arr [rand (0, i)] 交换位置。

需要注意,由于每次是随机一个 [0…i] 之间的下标,所以,在每一轮,是可以自己和自己交换的。

这个算法就是大名鼎鼎的 Knuth-Shuffle,即 Knuth 洗牌算法

理解算法

简单的只是用 5 个数字进行模拟。假设初始的时候,是按照 1,2,3,4,5 进行排列的。

2022070316101

那么,根据这个算法,首先会在这五个元素中选一个元素,和最后一个元素 5 交换位置。假设随机出了 2。

2022070316102

下面,计算 2 出现在最后一个位置的概率是多少?非常简单,因为是从 5 个元素中选的嘛,就是 1/5。实际上,根据这一步,任意一个元素出现在最后一个位置的概率,都是 1/5。

2022070316103

下面,根据这个算法,就已经不用管 2 了,而是在前面 4 个元素中,随机一个元素,放在倒数第二的位置。假设我们随机的是 3。3 和现在倒数第二个位置的元素 4 交换位置。

2022070316104

下面的计算非常重要。3 出现在这个位置的概率是多少?计算方式是这样的:

2022070316105

其实很简单,因为 3 逃出了第一轮的筛选,概率是 4/5,但是 3 没有逃过这一轮的选择。在这一轮,一共有 4 个元素,所以 3 被选中的概率是 1/4。因此,最终,3 出现在这个倒数第二的位置,概率是 4/5 * 1/4 = 1/5。

还是 1/5 !

实际上,用这个方法计算,任意一个元素出现在这个倒数第二位置的概率,都是 1/5。

相信聪明的同学已经了解了。我们再进行下一步,在剩下的三个元素中随机一个元素,放在中间的位置。假设我们随机的是 1

20220703161016

关键是:1 出现在这个位置的概率是多少?计算方式是这样的:

2022070316107

即 1 首先在第一轮没被选中,概率是 4/5,在第二轮又没被选中,概率是 3/4 ,但是在第三轮被选中了,概率是 1/3。乘在一起,4/5 * 3/4 * 1/3 = 1/5。

用这个方法计算,任意一个元素出现在中间位置的概率,都是 1/5。

这个过程继续,现在,我们只剩下两个元素了,在剩下的两个元素中,随机选一个,比如是 4。将 4 放到第二个位置

2022070316108

然后,4 出现在这个位置的概率是多少?4 首先在第一轮没被选中,概率是 4/5;在第二轮又没被选中,概率是 3/4;第三轮还没选中,概率是 2/3,但是在第四轮被选中了,概率是 1/2。乘在一起,4/5 * 3/4 * 2/3 * 1/2 = 1/5。

用这个方法计算,任意一个元素出现在第二个位置的概率,都是 1/5。

2022070316109

最后,就剩下元素 5 了。它只能在第一个位置呆着了。

那么 5 留在第一个位置的概率是多少?即在前 4 轮,5 都没有选中的概率是多少?

在第一轮没被选中,概率是 4/5;在第二轮又没被选中,概率是 3/4;第三轮还没选中,概率是 2/3,在第四轮依然没有被选中,概率是 1/2。乘在一起,4/5 * 3/4 * 2/3 * 1/2 = 1/5。

20220703161010

算法结束。在整个过程中,每一个元素出现在每一个位置的概率,都是 1/5 !所以,这个算法是公平的。

当然了,上面只是举例子。这个证明可以很容易地拓展到数组元素个数为 n 的任意数组。整个算法的复杂度是 O (n) 的。

转载说明

有哪些算法惊艳到了你? - 刘宇波的回答 - 知乎
https://www.zhihu.com/question/26934313/answer/743798587