?? 生成無重復的隨機數,注意,是不重復的序列.
?? 通常的生成隨機數的做法是不考慮重復的,因為即使重復也屬于概率意義上的正常情況.但某些情況下需要不重復的隨機數據,怎么辦呢?
?? 我想從大方向上來說,應該只有兩個方法.要么犧牲時間要么犧牲空間.講得不對或不完整,大家一定要指出來啊,謝謝.
?? 注意,下面均以在101~200的范圍內(設為b[100],它實際上是附加空間),從中產生10個不重復的隨機數(設為a[10]).
??
一.犧牲時間為代價
?? 這種方法不需要附加空間b數組.
?? 要產生一定范圍內不可重復的隨機數，把曾經生成的隨機數保存起來作為歷史數據。產生一個新的隨機數后在歷史數據搜索，若找到就重新產生一個新的再重復數據搜索；否則就認為已經找到了一個新的不同隨機數。
?? 可以預見,每個新產生的隨機數都要與前面所有的數比較.若重復,舍棄,再產生;否則,產生下一個.平均耗時n的平方量級.
?? 粗看起來，上面的程序似乎沒有什么問題，在執行過程中程序也能夠通過。但，仔細分析我們就會發現問題出在一個新產生的隨機數是否已經存在的判定上。既然是隨機數，那么從數學的角度來說在概率上，每次產生的隨機數 r就有可能相同，盡管這種可能性很小，但確是一個邏輯性與正確性的問題。因此，每次產生的新的隨機數r都有可能是數組random的前i-1個數中的某一個，也就是說程序在運行過程中由此可能會導致死循環!
??? 有人可能會爭辯說,這種概率很小嘛,幾乎為零.的確,但我要問,算法的五大特性是什么,其中兩大特性就是:確定性和有窮性.
??? 所以,怎么解決?犧牲空間.(稍后介紹)
二.犧牲空間為代價
?? 以下方法需要附加空間b數組.
?? (1)將范圍數組b[100](b[i]=100+i,不妨設數組下標從1開始)的每個元素設置一個標志位flag.初始均為flag=0;若某元素被選入到a數組中,則flag=1;顯然,以后再選到重復元素可以立刻判定是否已選.這不正是以空間換時間嗎?
?? 但是仍然有一個很嚴重的問題,在小規模輸入下,無疑它的表現是不錯的.但現在舉一個失敗的例子.
?? 在1~65536之間,選擇65500個不重復的隨機數.看看后面的隨機數,比如第65500個數(最后一個),它要在剩下的36個數中選擇才會有flag=0(根本不知道這36個數是什么);哼哼,概率36/65536.越到后面,隨機數越難產生,空間也換不了時間.
?? 改進:先在1~65536之間隨機選取36個數,刪除.將剩下的65500個數依次賦值給a[65500],然后打亂順序即可,如下偽碼:
1
for
?i?←?
1
?to?length[a]
2
???
do
?j?←?random()?
//
隨機產生一個a數組的下標
3
??????exchange?a[i]←→a[j]
//
交換a[i]與a[j]
4
? 當范圍數組與目標數組的大小非常接近時,上述算法非常有效,建議采用.
? (2)問題的最終解決.
?? 仍以最開始的那個例子來說,初始數組b[i]=100+i,a數組空.
?? 每次隨機生成數組b的一個下標subscript，然后取出它所對應的數據a[subscript],記下來.然后將數組b的最后一個數b[length]放到下標subscript的位置，同時將數組a長度減1。盡管前若干次生成的下標subscript隨機數有可能相同，但，因為每一次都把最后一個數填到取出的位置，因此，相同下標subscript對應的數卻絕不會相同，每一次取出的數都不會一樣，這樣，就保證了算法的確定性、有效性、有窮性.
? 偽碼算法如下:
?1
lower?←?
101
?2
upper?←?
200
?3
for
?i?←?
1
?to?upper
-
lower
+
1
?4
????
do
?b[i]
=
lower
+
i
-
1
?5
for
?i←
1
?to?length[a]
?6
????
do
?subscript?
=
?(
int
)(length[b]
*
Rnd?
+
?lower)
//
隨機產生b數組的一個下標,Rnd產生0~1隨機數
?7
???????temp?←?b[subscript]
?8
???????b[subscript]?←?b[length[b]]
?9
???????length[b]
--
;
10
???????a[i]
=
temp;
11
? 這個算法我認為是很不錯的.
?
如果大家有更好的想法解決不重復的隨機數,歡迎探討!
posted on 2006-11-12 12:05
哈哈 閱讀(4332)
評論(12) 編輯 收藏 引用