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