這個(gè)需求應(yīng)該是很常見的吧，需要從 0 到
n 之間選 k 個(gè)不重復(fù)的
數(shù)組成
一個(gè)序列。
我最早遇到這個(gè)問題是在給校ACM比賽出題時(shí)，需要
隨機(jī)產(chǎn)生一些測(cè)試數(shù)據(jù)，當(dāng)時(shí)我想的是用
一個(gè)輔助數(shù)組記錄之前已經(jīng)產(chǎn)生的
隨機(jī)數(shù)，如果當(dāng)前產(chǎn)生的
隨機(jī)數(shù)已經(jīng)出現(xiàn)過就再重新
隨機(jī)。
顯然這樣的實(shí)現(xiàn)效率是很低的，設(shè)想從10000個(gè)
數(shù)中
隨機(jī)產(chǎn)生10000個(gè)
數(shù)的序列，當(dāng)前面9999個(gè)
數(shù)已經(jīng)確定了時(shí)，最后
一個(gè)數(shù)被
隨機(jī)到的概率是 0.0001，也就是說大概需要調(diào)用
隨機(jī)函數(shù)10000
次才會(huì)產(chǎn)生。類似的，第9999個(gè)
數(shù)被
隨機(jī)到的概率是0.0002……
.....
我后來采用了一個(gè)改進(jìn)的辦法是，如果當(dāng)前產(chǎn)生的隨機(jī)數(shù)a已經(jīng)在之前產(chǎn)生過了，就順序去找比a小的數(shù)，直到找到一個(gè)之前沒有產(chǎn)生過的數(shù)，如果找不到就找比a大的數(shù)。
可以看到這樣的改進(jìn)節(jié)省了大量的時(shí)間，但是這樣產(chǎn)生的已經(jīng)不是隨機(jī)數(shù)序列了！
試想從1，2，3，4中隨機(jī)挑選2個(gè)數(shù)，假如第一次選出來的是3，那么第二次再選的話，選中2的概率就變成了1/2，因?yàn)楫?dāng)隨機(jī)出來的數(shù)為2或3時(shí)，我們都選擇2。
在我遇到的應(yīng)用中，因?yàn)閷?duì)隨機(jī)數(shù)序列的“隨機(jī)性”要求不是很高，所以湊合著用了上述辦法。
直到今天在《Programming pearls》里看到這個(gè)很完美的辦法：
for(i = 0; i < n; i++)
{
x[i] = i;
}
for(i = 0; i < k; i++)
{
t = rand(i,n-1);
swap(x[i], x[t]);
out(x[i]);
}
其中，rand(a,b)產(chǎn)生一個(gè) a 到 b 之間的隨機(jī)數(shù)，swap(a,b)交換a和b的值，out(a)把a(bǔ)輸出作為結(jié)果。
我們來看看這個(gè)算法的完美之處吧！
首先，x數(shù)組里把0到n-1的所有數(shù)都存儲(chǔ)了，而最后輸出的都是x數(shù)組里的值，所以滿足輸出的數(shù)是k個(gè)0到n-1的數(shù)。
然后，我們對(duì)于第 i 次隨機(jī)，產(chǎn)生一個(gè) i 到 n-1 的下標(biāo) t ，并把x[t] 和x[i]交換，將其輸出，這樣每次產(chǎn)生的數(shù)都是之前沒有出現(xiàn)過的數(shù)，因?yàn)橹俺霈F(xiàn)過的數(shù)都在x[0] 到 x[i-1]里呢！這樣就保證了輸出數(shù)據(jù)的不重復(fù)性。
最后，我們考察輸出數(shù)據(jù)的“隨機(jī)性”，顯然，因?yàn)榻粨Q操作，使得所有沒有出現(xiàn)過的數(shù)都在x[i] 到 x[n-1]中存著呢，所以被選中的概率相等。
寫完上面這些文字之后，我在想，這樣經(jīng)典的算法，應(yīng)該是早就已經(jīng)出現(xiàn)了，但是我竟然還不知道，這樣看來，我百度實(shí)習(xí)面試遭鄙視也就是很自然的了，這也算是我之前的一個(gè)毛病，喜歡遇到問題才去想怎么解決，沒問題就很少看相關(guān)的書或資料，而對(duì)于自己能解決的問題(比如上面說的這個(gè)湊合著能用的問題)，我又懶得去找更好的甚或是標(biāo)準(zhǔn)的解決方法，所以才造成了我現(xiàn)在的知識(shí)局限，以后要多看書，多想問題，盡量多的積累知識(shí)吧……
posted on 2010-02-21 14:21
北國(guó)狼人的BloG 閱讀(4135)
評(píng)論(1) 編輯 收藏