本文主要是介绍面试随机数生成函数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
面试随机数生成函数
相关的面试中涉及的随机数生成、以及概率的有关问题的讨论,请参阅 如何通过投掷一枚硬币产生各种概率。
解决这类题有两大窍门:
-
0-1区间上的均匀分布,和 if 相结合实现对某一概率的要求;
-
多次采样,并不限制为1次;
-
适当地取舍;
首先来看一道笔试题:
实现某一随机数生成函数 f()f(),返回0的概率是60%,返回1的概率是40%(有偏置型硬币)。
import random
def bias_coin():p = random.random()return 0 if p < 0.6 else 1
- 1
- 2
- 3
- 4
假设此时 f()f()已知,根据 f()f()求另一随机数生成函数 g()g(),使返回 0,10,1的概率均为 0.5, 0.5.
多次取样,求joint probability(联合概率)。对本例而言,调用两次 f()f()即可,此时会出现4中结果(构成样本空间),(0, 0), (0, 1), (1, 0), (1, 1),其中出现(0, 1)(0.6*0.4)和(1, 0)(0.4*0.6)的概率是一致的,据此可构造等概率事件。
def g():while True:a, b = bias_coin(), bias_coin()if (a, b) == (0, 1):return 1if (a, b) == (1, 0):return 0
- 1
- 2
- 3
- 4
- 5
- 6
- 7
我们接着看如何符合某一概率分布(离散型)进行采样,而不限于
如下的伯努利分布(最为简单的0-1分布),比如三个离散值 [(1,0.3),(2,0.4),(3,0.3)][(1,0.3),(2,0.4),(3,0.3)]。
def bernoulli(p):u = random.random()return 1 if u < p else 0
- 1
- 2
- 3
此时我们需要重新定义该函数形式:
def withProbRandomPick(prob_dist):r = random.random()s = 0for prob in prob_dist:s += prob[1]# 这一步相加很妙,很妙if r < s:return prob[0]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
简单验证:
prob_dist = [(1, .3), (2, .4), (3, .3)]
from collections import defaultdict
cnt = defaultdict(int)
N = 10**6
for i in range(N):cnt[withProbRandomPick(pro_dist)] += 1
for n in cnt:print(n, cnt[n]/N)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
输出为:
1 0.30159
2 0.39829
3 0.30012
- 1
- 2
- 3
- 4
《程序员面试金典第5版》(Cracking the Coding Interview) 也有一道给定一个随机数生成函数生成另一个随机数函数的题目;
给定rand5(),实现一个方法rand7()。也即,给定一个产生0到4(含)随机数方法,编写一个产生0到6(含)随机数的方法。(P105)
解题的关键在于确保产生每一个数的概率相等。我们首先来分析:
-
rand5(): [0, 1, 2, 3, 4]
-
2*rand5(): [0, 2, 4, 6, 8]
-
rand5() + rand5():(rand5()+rand5()不仅与2*rand5()取值范围不同)最终的取值范围在[0, 8],但取每一个值的概率并不相等,比如0=0+0, 4=4+0=0+4=2+2=1+3=3+1,对应于各种情况
-
先说一下为什么rand3*3+rand3();这一步其实是要先产生[0,9)的随机数。多个rand3相加并不能产生等概率的随机数。这个方法很有意思,先将rand3*3,产生等概率的0,3,6,而0与3之间,3与6之间正好相差3,正好是一个rand3()的范围,所以rand3*3+rand3正好把0与3之间的部分给填上了,而且由于rand3产生的是等概率的,所以生成的也是等概率的,于是就变成了[0,9)之间的等概率随机数。而乘数3必须是rand3()的上界,这样正好可以填充完整。同理,rand5生成rand7,代码如下。
-
5*rand5() + rand5():取值范围在[0, 24],取每一个值的概率达到完美的相等;
# 这里不妨给出rand5()的简单实现
def rand5():p = random.random()return int(p*5)
- 1
- 2
- 3
- 4
# 根据rand5(),得rand7()的实现
def rand7():while True:x = 5*rand5()+rand5()if x < 21:return x%7
- 1
- 2
- 3
- 4
- 5
- 6
稍加变形,给定rand7(),如何实现rand5()呢?
关键还在于确保产生的每一个值的概率相等。
形式上与上面的方法相同:7*rand7()+rand7()
# 也姑且给出rand7()的简单实现
def rand7():p = random.random()return int(7*p)
- 1
- 2
- 3
- 4
def rand5():while True:x = 7*rand7()+rand7()while x < 45:return x%5
#rand_m to rand_n
def rand_n():while True:x = m*rand_m()+rand_m()if x < ((m*m)/n)*n:return x%n
这篇关于面试随机数生成函数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!