隨機(jī)算法涉及大量概率論知識(shí)北苟，有時(shí)候難得去仔細(xì)看推導(dǎo)過(guò)程以躯，當(dāng)然能夠完全了解推導(dǎo)的過(guò)程自然是有好處的蟆盐，如果不了解推導(dǎo)過(guò)程移必，至少記住結(jié)論也是必要的室谚。本文總結(jié)最常見(jiàn)的一些隨機(jī)算法的題目，是幾年前找工作的時(shí)候?qū)懙摹Ｐ枰f(shuō)明的是秒赤，這里用到的隨機(jī)函數(shù)都假定它能隨機(jī)的產(chǎn)生范圍[a,b]內(nèi)的整數(shù)猪瞬，即產(chǎn)生每個(gè)整數(shù)的概率相等。（雖然在實(shí)際中并不一定能實(shí)現(xiàn)入篮，不過(guò)陈瘦，誰(shuí)在乎呢？這個(gè)世界都是這么隨機(jī)）
1 隨機(jī)排列數(shù)組
假設(shè)給定一個(gè)數(shù)組A潮售，它包含元素1到N痊项，我們的目標(biāo)是構(gòu)造這個(gè)數(shù)組的一個(gè)隨機(jī)排列。
一個(gè)常用的方法是為數(shù)組每個(gè)元素A[i]賦一個(gè)隨機(jī)的優(yōu)先級(jí)P[i]酥诽，然后依據(jù)優(yōu)先級(jí)對(duì)數(shù)組進(jìn)行排序线婚。比如我們的數(shù)組為A={1， 2盆均， 3， 4}漱逸，如果選擇的優(yōu)先級(jí)數(shù)組為P={36泪姨， 3， 97饰抒， 19}肮砾，那么就可以得到數(shù)列B={2, 4, 1, 3}，因?yàn)?的優(yōu)先級(jí)最高（為97）袋坑，而2的優(yōu)先級(jí)最低（為3）仗处。這個(gè)算法需要產(chǎn)生優(yōu)先級(jí)數(shù)組，還需使用優(yōu)先級(jí)數(shù)組對(duì)原數(shù)組排序枣宫，這里就不詳細(xì)描述了婆誓，還有一種更好的方法可以得到隨機(jī)排列數(shù)組。
產(chǎn)生隨機(jī)排列數(shù)組的一個(gè)更好的方法是原地排列給定數(shù)組（in-place）也颤，可以在O(N)的時(shí)間內(nèi)完成洋幻。偽代碼如下：
RANDOMIZE-IN-PLACE ( A , n ) for i ←1 to n do swap A[i] ? A[RANDOM(i , n )]
如代碼中所示，第i次迭代時(shí)翅娶，元素A[i]是從元素A[i]到A[n]中隨機(jī)選取的文留，在第i次迭代后，我們就再也不會(huì)改變A[i]竭沫。
A[i]位于任意位置j的概率為1/n燥翅。這個(gè)是很容易推導(dǎo)的，比如A[1]位于位置1的概率為1/n蜕提，這個(gè)顯然森书，因?yàn)锳[1]不被1到n的元素替換的概率為1/n，而后就不會(huì)再改變A[i]了。而A[1]位于位置2的概率也是1/n拄氯，因?yàn)锳[1]要想位于位置2躲查，則必須在第一次與A[k]交換(k=2...n)，同時(shí)第二次A[2]與A[k]替換译柏，第一次與A[k]交換的概率為(n-1)/n镣煮，而第二次替換概率為1/(n-1)，所以總的概率是(n-1)/n * 1/(n-1) = 1/n鄙麦。同理可以推導(dǎo)其他情況典唇。
當(dāng)然這個(gè)條件只能是隨機(jī)排列數(shù)組的一個(gè)必要條件，也就是說(shuō)胯府，滿足元素A[i]位于位置j的概率為1/n不一定就能說(shuō)明這可以產(chǎn)生隨機(jī)排列數(shù)組介衔。因?yàn)樗赡墚a(chǎn)生的排列數(shù)目少于n！骂因，盡管概率相等炎咖，但是排列數(shù)目沒(méi)有達(dá)到要求，算法導(dǎo)論上面有一個(gè)這樣的反例寒波。
算法RANDOMIZE-IN-PLACE可以產(chǎn)生均勻隨機(jī)排列乘盼，它的證明過(guò)程如下：
- 首先給出k排列的概念，所謂k排列就是從n個(gè)元素中選取k個(gè)元素的排列俄烁，那么它一共有n!/(n-k)!個(gè)k排列绸栅。
- 循環(huán)不變式：for循環(huán)第i次迭代前，對(duì)于每個(gè)可能的i-1排列页屠，子數(shù)組A[1...i-1]包含該i-1排列的概率為(n-i+1)! / n!粹胯。
- 初始化：在第一次迭代前，i=1辰企，則循環(huán)不變式指的是對(duì)于每個(gè)0排列风纠，子數(shù)組A[1...i-1]包含該0排列的概率為(n-1+1)! / n! = 1。A[1...0]為空的數(shù)組蟆豫，0排列則沒(méi)有任何元素议忽，因此A包含所有可能的0排列的概率為1。不變式成立十减。
- 維持：假設(shè)在第i次迭代前栈幸，數(shù)組的i-1排列出現(xiàn)在A[1...i-1]的概率為(n-i+1) !/ n!，那么在第i次迭代后帮辟，數(shù)組的所有i排列出現(xiàn)在A[1...i]的概率為(n-i)! / n!速址。下面來(lái)推導(dǎo)這個(gè)結(jié)論：
考慮一個(gè)特殊的i排列p = {x1, x2, ... xi}，它由一個(gè)i-1排列p' =?{x1, x2,..., xi?1?}后面跟一個(gè)xi構(gòu)成由驹。設(shè)定兩個(gè)事件變量E1和E2：
E1為該算法將排列p'放置到
A[1...i-1]的事件芍锚，概率由歸納假設(shè)得知為Pr(E1) = (n-i+1)! / n!昔园。E2為在第i次迭代時(shí)將xi放入到A[i]的事件。
因此我們得到i排列出現(xiàn)在A[1...i]的概率為Pr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}.而Pr {E2 | E1} = 1/(n ? i + 1)并炮，所以
Pr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}= 1 /(n ? i + 1) * (n ? i + 1)! / n! = (n ? i )! / n!默刚。結(jié)束：結(jié)束的時(shí)候i=n+1，因此可以得到A[1...n]是一個(gè)給定n排列的概率為1/n逃魄！荤西。
擴(kuò)展
如果上面的隨機(jī)排列算法寫成下面這樣，是否也能產(chǎn)生均勻隨機(jī)排列伍俘？
PERMUTE-WITH-ALL( A , n ) for i ←1 to n do swap A[i] ?A[RANDOM(1 , n )]
注意邪锌，該算法不能產(chǎn)生均勻隨機(jī)排列。假定n=3癌瘾，則該算法可以產(chǎn)生3*3*3=27個(gè)輸出觅丰，而3個(gè)元素只有3!=6個(gè)不同的排列，要使得這些排列出現(xiàn)概率等于1/6妨退，則必須使得每個(gè)排列出現(xiàn)次數(shù)m滿足m/27=1/6妇萄，顯然，沒(méi)有這樣的整數(shù)符合條件咬荷。而實(shí)際上各個(gè)排列出現(xiàn)的概率如下嚣伐，如{1,2,3}出現(xiàn)的概率為4/27，不等于1/6萍丐。
2 隨機(jī)選取一個(gè)數(shù)字
題目
給定一個(gè)未知長(zhǎng)度的整數(shù)流，如何隨機(jī)選取一個(gè)數(shù)放典？（所謂隨機(jī)就是保證每個(gè)數(shù)被選取的概率相等）
解法1
如果數(shù)據(jù)流不是很長(zhǎng)逝变，可以存在數(shù)組中，然后再?gòu)臄?shù)組中隨機(jī)選取奋构。當(dāng)然題目說(shuō)的是未知長(zhǎng)度壳影，所以如果長(zhǎng)度很大不足以保存在內(nèi)存中的話會(huì)很麻煩。這種解法有其局限性弥臼。
解法2
如果數(shù)據(jù)流在第1個(gè)數(shù)字后結(jié)束宴咧，那么必選第1個(gè)數(shù)字。
如果數(shù)據(jù)流在第2個(gè)數(shù)字后結(jié)束径缅，那么我們選第2個(gè)數(shù)字的概率為1/2掺栅，我們以1/2的概率用第2個(gè)數(shù)字替換前面選的隨機(jī)數(shù)，得到新的隨機(jī)數(shù)纳猪。
.........
如果數(shù)據(jù)流在第n個(gè)數(shù)字后結(jié)束氧卧，那么我們選擇第n個(gè)數(shù)字的概率為1/n，即我們以1/n的概率用第n個(gè)數(shù)字替換前面選的隨機(jī)數(shù)氏堤，得到新的隨機(jī)數(shù)沙绝。
一個(gè)簡(jiǎn)單的方法就是使用隨機(jī)函數(shù)f(n)=bigrand()%n，其中bigrand()返回很大的隨機(jī)整數(shù)，當(dāng)數(shù)據(jù)流到第n個(gè)數(shù)時(shí)闪檬，如果f(n)==0星著，則替換前面的已經(jīng)選的隨機(jī)數(shù)，這樣可以保證每個(gè)數(shù)字被選中的概率都是1/n粗悯。如當(dāng)n=1時(shí)虚循，則f(1)=0,則選擇第1個(gè)數(shù)，當(dāng)n=2時(shí)为黎，則第2個(gè)數(shù)被選中的概率為1/2邮丰，以此類推，當(dāng)數(shù)字長(zhǎng)度為n時(shí)铭乾，第n個(gè)數(shù)字被選中的概率為1/n剪廉。
3 隨機(jī)選取M個(gè)數(shù)字
題目
程序輸入包含兩個(gè)整數(shù)m和n，其中m<n炕檩，輸出是0~n-1范圍內(nèi)的m個(gè)隨機(jī)整數(shù)的有序列表斗蒋，不允許重復(fù)。從概率角度來(lái)說(shuō)笛质，我們希望得到?jīng)]有重復(fù)的有序選擇泉沾，其中每個(gè)選擇出現(xiàn)的概率相等。
解法1
先考慮個(gè)簡(jiǎn)單的例子妇押，當(dāng)m=2跷究，n=5時(shí)，我們需要從0~4這5個(gè)整數(shù)中等概率的選取2個(gè)有序的整數(shù)敲霍，且不能重復(fù)俊马。如果采用如下條件選取：bigrand() % 5 < 2肩杈，則我們選取0的概率為2/5柴我。但是我們不能采取同樣的概率來(lái)選取1，因?yàn)檫x取了0后扩然，我們應(yīng)該以1/4的概率來(lái)選取1艘儒，而在沒(méi)有選取0的情況下，我們應(yīng)該以2/4的概率選取1夫偶。選取的偽代碼如下：
select = m
remaining = n
for i = [0, n)
if (bigrand() % remaining < select)
print i
select--
remaining--
只要滿足條件m<=n界睁，則程序輸出m個(gè)有序整數(shù)，不多不少兵拢。不會(huì)多選晕窑，因?yàn)槊窟x擇一個(gè)數(shù)，select--卵佛，這樣當(dāng)select減到0后就不會(huì)再選了杨赤。同時(shí)敞斋，也不會(huì)少選，因?yàn)槊看味紩?huì)remaining--疾牲，當(dāng)select/remaining=1時(shí)植捎，一定會(huì)選取一個(gè)數(shù)。每個(gè)子集被選擇的概率是相等的阳柔，比如這里5選2則共有C(5,2)=10個(gè)子集焰枢，如{0，1}舌剂，{0济锄，2}...等，每個(gè)子集被選中的概率都是1/10霍转。更一般的推導(dǎo)荐绝，n選m的子集數(shù)目一共有C(n,m)個(gè)，考慮一個(gè)特定的m序列避消，如0...m-1低滩，則選取它的概率為m/n * (m-1)/(n-1)*....1/(n-m+1)=1/C(n,m)，可以看到概率是相等的岩喷。C++語(yǔ)言實(shí)現(xiàn)代碼如下恕沫，該算法時(shí)間復(fù)雜度為O(n)。
void genknuth(int m, int n)
{
for (int i=0; i<n; i++)
if (bigrand() % (n-i) < m) { //n-i中i每次加1纱意，相當(dāng)于remaining每次減1
cout << i << endl;
m--; //選取的數(shù)目減1
}
}
解法2
在初始為空的集合中插入隨機(jī)整數(shù)婶溯，直到數(shù)目達(dá)到m。由于每次插入操作需要O(logm)的時(shí)間偷霉，遍歷集合需要O(m)的時(shí)間爬虱，該算法總共需要O(mlogm)的實(shí)際。代碼：
void gensets(int m, int n)
{
set<int> S;
while (S.size() < m)
S.insert(bigrand() % n);
set<int>::iterator it;
for (it = S.begin(); it != S.end(); it++)
cout << *it << endl;
}
解法3
采用前面隨機(jī)排列數(shù)組的思想腾它，先對(duì)前m個(gè)數(shù)字進(jìn)行隨機(jī)排列，然后排序這m個(gè)數(shù)字并輸出即可死讹。代碼省略瞒滴。
4 rand7()生成rand10()問(wèn)題
請(qǐng)參見(jiàn)http://blog.csdn.net/sgbfblog/article/details/7753012
5 趣味概率題
1）生男生女問(wèn)題：在重男輕女的國(guó)家里，男女的比例是多少赞警？在一個(gè)重男輕女的國(guó)家里妓忍，每個(gè)家庭都想生男孩，如果他們生的孩子是女孩愧旦，就再生一個(gè)世剖，直到生下的是男孩為止。這樣的國(guó)家笤虫，男女比例會(huì)是多少旁瘫？
- 答案：還是1：1祖凫。在所有出生的第一個(gè)小孩中，男女比例是1：1酬凳；在所有出生的第二個(gè)小孩中惠况，男女比例是1：1；.... 在所有出生的第n個(gè)小孩中宁仔，男女比例還是1：1稠屠。所以總的男女比例是1：1。
2）約會(huì)問(wèn)題：兩人相約5點(diǎn)到6點(diǎn)在某地會(huì)面翎苫，先到者等20分鐘后離去权埠，求這兩人能夠會(huì)面的概率。
- 答案：設(shè)兩人分別在5點(diǎn)X分和5點(diǎn)Y分到達(dá)目的地煎谍，則他們能夠會(huì)面的條件是|X-Y| <= 20攘蔽，而整個(gè)范圍為S={(x, y): 0 =< x <= 60, 0=< y <= 60}，所以會(huì)面的情況為圖中表示的面積粱快，概率為(60^2 - 40^2) / 60^2 = 5/9秩彤。
3）帽子問(wèn)題：有n位顧客，他們每個(gè)人給餐廳的服務(wù)生一頂帽子事哭，服務(wù)生以隨機(jī)的順序歸還給顧客漫雷，請(qǐng)問(wèn)拿到自己帽子的顧客的期望數(shù)是多少？
- 答案：使用指示隨機(jī)變量來(lái)求解這個(gè)問(wèn)題會(huì)簡(jiǎn)單些鳍咱。定義一個(gè)隨機(jī)變量X等于能夠拿到自己帽子的顧客數(shù)目降盹，我們要計(jì)算的是E[X]。對(duì)于i=1, 2 ... n谤辜，定義Xi =I {顧客i拿到自己的帽子}蓄坏，則
X=X1+X2+...Xn。由于歸還帽子的順序是隨機(jī)的丑念，所以每個(gè)顧客拿到自己帽子的概率為1/n涡戳，即Pr(Xi=1)=1/n，從而E(Xi)=1/n脯倚，所以E(X)=E(X1+X2+...Xn)=E(X1)+E(X2)+...E(Xn)=n*1/n = 1渔彰。即大約有1個(gè)顧客可以拿到自己的帽子。4）生日悖論：一個(gè)房間至少要有多少人推正，才能使得有兩個(gè)人的生日在同一天恍涂？答案：對(duì)房間k個(gè)人中的每一對(duì)(i, j)定義指示器變量Xij = {i與j生日在同一天} ，則i與j生日相同時(shí)植榕，Xij=1再沧，否則Xij=0。兩個(gè)人在同一天生日的概率Pr(Xij=1)=1/n尊残。則用X表示同一天生日的兩人對(duì)的數(shù)目炒瘸，則E(X)=E(∑ki=1∑kj=i+1Xij) = C(k,2)*1/n = k(k-1)/2n淤堵，令k(k-1)/2n >=1， 可得到k>=28什燕，即至少要有28個(gè)人粘勒，才能期望兩個(gè)人的生日在同一天。
5）如果在高速公路上30分鐘內(nèi)看到一輛車開過(guò)的幾率是0.95屎即，那么在10分鐘內(nèi)看到一輛車開過(guò)的幾率是多少庙睡？(假設(shè)常概率條件下)
- 答案：假設(shè)10分鐘內(nèi)看到一輛車開過(guò)的概率是x，那么沒(méi)有看到車開過(guò)的概率就是1-x技俐，30分鐘沒(méi)有看到車開過(guò)的概率是(1-x)3乘陪，也就是0.05。所以得到方程(1-x)3 = 0.05 雕擂，解方程得到x大約是0.63啡邑。
參考資料
- 算法導(dǎo)論
- 編程珠璣2
- http://blog.csdn.net/wxwtj/article/details/6621430
