网上流行几条面试题, 都和经典的采样洗牌问题有关, 网上每过一段时间都有哥们拿出来问一下. 正好最近在翻的 TAoCP Vol 2 上有详细专门的讲解, 因此在此一并介绍.
这几道面试题是:
1. Given a random number generator which can generate the number in range (1,5) uniformly. How can you use it to build a random number generator which can generate the number in range (1,7) uniformly?
(http://discuss.joelonsoftware.com/default.asp?interview.11.489564.8)
-
Generate a random permutation for a deck of cards.
-
Given a long log file (not sure how long), pick 1000 items evenly from them. (Google Interview)
其中, 第一条是随机数的生成问题. 第二条是生成一个序列的随机排列的问题, 第三条等价于生成一个序列的随机组合的问题. 实质上洗牌问题就是从集合中选取随机排列, 而采样问题就是从集合中选取随机组合.
第一条的解法要用到拒绝采样定理. 简单的说, 把 1-5 的随机数发生器用两次, 拼成一个5进制的数, 就是1-25. 将这 1-25 平均分配的25种情况映射到7种情况上, 问题就解决了. 因为21是7的倍数, 我们可以每三个映射到一个, 即1-3 映射到1, …, 19-21 映射到7. 可见, 这些情况之间的概率是一样的. 那么, 要是拼成的数字正好是 22-25 这四个呢? 有两种方法, 第一种是丢弃这个数字, 从头再来, 直到拼成的数字在1-21之间. 因为这个是个概率算法, 不能保证每次都能落在1-21, 所以采样的密度不高. 还有一种方法, 是说, 假如落到了 22-25, 那这次的采样结果就用上次的. 可以证明, 这看上去两个互相矛盾的算法, 结果都能均等的得到等概率的分布. (前者叫做 Reject Sampling, 后者叫做 Metropolis Algorithm, 都是数学物理模拟里面常用的方法)
第二条的解法很简单, 从后往前第k步的时候, 每次取一个1-52k (假如牌有52张) [感谢读者评论指出这个错误 不是1-52, 而是1-k] 的随机数 j, 交换 k 和 j. 这样, 每一位都是等概率的被交换, 最后的排列也是等概率的得到.
这个方法有一个趣闻. 我们知道, 计算机里的随机数发生器是伪随机数发生器. 伪随机数发生器的原理是用线性同余实现的, 即本次的随机数 乘以一个常数, 加上另一个常数, 再对一个大数c求同余. 我们可以把从一个随机数到下一个随机数的映射看成一个函数, 这个函数是必然形成循环的 (您把这个操作和集合整体当成循环群理解也是对的, 因为好的伪随机数发生器都设计得使得所有的数是各态遍历的). 这个循环的周期, 最长就是就是c. 所以, 如果您用伪随机数发生器来生成以上的排列的话, 只会得到最多 c 种不同的交换方案. 假设我们使用 32 位机器, 那么最大的可以用在做同余的c 就是 \(2^{32}\). 可是 13! 就已经是这个数量级了, 更不要说是 52 的阶乘. 这就意味着, 用计算机里的随机数发生器, 只能生成总体可能排列中极其有限的一部分. 所以, 假如您在电脑上玩扑克牌, 而扑克牌的洗牌算法又正好是上面我们说的那种的话, 您可能一辈子也抓不到某种组合. 这个不是概率很小的问题, 而是完全不可能. (此例来自 TAoCP, Vol 2)
第三条也不难, 虽然听上去吓人. 本质上只需要知道在已经处理了前 t (\(t \ge 1000\))个的情况下, 第 t +1 个被选中的概率. 实际上就是 1000/(t+1). 因此, 用这个概率去替换已经选中的1000个当中的某个. 可以证明, 任何时间停下来, 算法都是等概率的挑出了前面 t 个里面的1000 个. 这种任何时间能停下来还能获得正确结果的算法, 叫做 Anytime Algorithm, 在计算机科学领域随处可见, 尤其是 AI Search 方面.
第三条的算法在 TAoCP 第二卷里面交代得更加全面, 因为考虑了这 1000 个记录在内存里面放不下的情况. 这时候, 一个叫做 reservoir 的缓存被引入. 每次仅仅把选中的记录加入 reservoir, 而只保留记录在其中的序号. 在序号的数据结构上作替换, 最后, 按照最终留下来的那些序号, 再走一遍 reservoir, 就得到了要选的记录. 这个采样的方法在分析不定长网络日志的时候比较有用, 所以也是 Google 亲睐的面试题.
采样和洗牌的更多内容, 请参考 TAoCP Vol 2. 3.4.2.