20.2 写一个随机洗牌函数

题目

写一个随机洗牌函数。要求洗出的52!种组合都是等概率的。 也就是你洗出的一种组合的概率是1/(52!)。假设已经给你一个完美的随机数发生器。

解答

这是一道非常有名的面试题,及非常有名的算法——随机洗牌算法。

最直观的思路是什么?很简单,每次从牌堆中随机地拿一张出来。那么, 第一次拿有52种可能,拿完后剩下51张;第二次拿有51种可能,第三次拿有50种可能, …,一直这样随机地拿下去直到拿完最后1张,我们就从52!种可能中取出了一种排列, 这个排列对应的概率是1/(52!),正好是题目所要求的。

接下来的问题是,如何写代码去实现上面的算法?假设扑克牌是一个52维的数组cards, 我们要做的就是从这个数组中随机取一个元素,然后在剩下的元素里再随机取一个元素… 这里涉及到一个问题,就是每次取完元素后,我们就不会让这个元素参与下一次的选取。 这个要怎么做呢。

我们先假设一个5维数组:1,2,3,4,5。如果第1次随机取到的数是4, 那么我们希望参与第2次随机选取的只有1,2,3,5。既然4已经不用, 我们可以把它和1交换,第2次就只需要从后面4位(2,3,1,5)中随机选取即可。同理, 第2次随机选取的元素和数组中第2个元素交换,然后再从后面3个元素中随机选取元素, 依次类推。

代码如下:

关于如何测试随机洗牌程序,推荐阅读耗叔的文章: 如何测试洗牌程序

类似问题:如何在根据随机数生成函数Random(),得到一个包含50个元素的数组(要求:这50个元素包含1~50这50个数,也即每个数刚好出现一次,且每个元素在数组中的位置是随机的)

文/Hawstein

1 Likes

你目前的身份是游客,评论请输入昵称和电邮!