在面试中还遇到了另一个问题

0.random selection问题

54张扑克牌,随机发放。 (注:可以使用系统的伪随机数字列)
如何实现?

看起来是经典的Randomized algorithm问题。

1.关于扑克牌乱序输出的简易算法

我们先回归这个问题本身。
我在[6]中找到了2种简单的算法。

(1) 随机抽取2个数字a,b ∈ (0,53) ,对54张牌的a,b位置的牌的位置进行对调。反复N次即可。
(2) 用hash map,随机抽取一个数字a ∈ (0, 53),然后判断这个数字是否被选中,如若被选中,重新抽取;如果没选中,输出。

那么在这个的基础上,事实上可以对(1)方法进行优化,下面是我对(1)的优化。
几乎是本能的去优化了= =””“
不知道为什么网上怎么好多都是(1)(2)这两个版本,比如[7]也是这样的。不过仔细的找了之后,发现也是有和我同样想法的博客[8])

我们先假设扑克牌是放置在(0, 53)的一列数组中。
随机抽取一个数字a ∈ (0, k)。k的初始值是53。
当第一次抽取数字a之后,对于抽取的数字a的位置的牌和位置53的牌位置进行对调。
然后k = k-1。如此循环直到k == 0为止。
那么我们可以将数组从53开始输出,一直到0为止,就可以输出一套随机数组了。
我的这个解说可能有点难以理解,我写一下伪代码好了。

// a是在[0, 54)的半闭区间随机取整数值。
a = random[0, 54) 
k = 53
cards = [0, 1, 2, ..., 53]
while True
  if k == 0 break
  swap(cards[a], cards[k])
  a = random[0, k)
  k--

// OUTPUT
k = 53
while True
  if k == -1 break
  print cards[k]
  k--

这样就只需要一个随机数,一个数组就可以做到了。
真的没想到这问题这么简单就是2个for文的事儿… 这样看起来这个问题根本用不到Randomized algorithm理论

2. 更深入一些

这个算法在pro con中常见的实现有两种:

  • Las Vegas Algorithm [4] 计算时间不固定。
  • Monte Carlo Algorithm [5] 结果未必正确。(可能分布不是平均的)

在[1]的36页里面提出,作为Randomized algorithm的出题者,本身也是有相当的挑战的。
出题的条件放宽的话,导致很可能让heuristic algothrim也能通过。如果过分严格,乱序本身也可能很难通过。

3.今后课题

根据[3]的某大学教材,进行系统的Randomized algorithm学习。

[1]slide share プロコンでの乱択アルゴ
[2]wikipedia 乱択アルゴリズム
[3]乱択アルゴリズム 山本真基
[4]wikipedia ラスベガス法 Las Vegas algorithm
[5]wikipedia モンテカルロ法 Monte Carlo
[6]一个简单的扑克牌洗牌算法|无重复
[7]高效生成随机数组——已发《电脑报》
[8]扑克牌的完美洗牌算法


Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)