1樓:悽臨雨
設計一種一一對映的函式f(x):0~21億一一對映到0~21億
然後取前n個x,然後f(隨機種子+1)……f(隨機種子+n)就是你要的前n個不相同的隨機數。
至於如何產生這樣的函式?
我們知道十進位制是A * 10000 + B * 1000 …… + E * 1。
對位的順序做交換:交換D和E,會變成00,10,20,30,……90,01,11,……91,02……
對某個位上的某一些數字做旋轉,比如把1和3做交換,4567變成7654等
這樣我們可以得到10進製上的一一對映。
如果不是十進位制而是不固定進製呢?比如100變成10、5、2進製,然後對每個位上做順序交換、旋轉,這樣會提高「隨機」程度。
把21億左右,因式分解,變成a*b*c*d*e……這樣我們把0~21億左右,變成了不固定進製
對這些位做交換順序和旋轉,根據標準隨機函式決定如何交換和旋轉,這樣你能得到乙個「隨機」數列,能保證不重複。
此演算法複雜度每產生乙個數字需要「已定規則」次數的計算,空間複雜度也極低。
對於2^32次方,因式分解也全是2,所以隨機效果不太明顯,所以數字空間上限最好不是如此規整的數字。
2088666580 =2*2*5*7*11*13*17*19*19*17 < 2147483648
比較接近21億了
2樓:
對乙個 0-2100000000 的 array 用 Knuth Shuffle,然後取前 x 個數。
用 APL 的 deal 演示一下。12?
2100000000
1472916175
2099753205
113842893
72631085
1148749129
1858416175
1388341335
1190080393
2067873817
329196653
1577121087
390888167
find number less than 10000(210000
?2100000000
)3272
6358
(210000
?2100000000
)819
Knuth Shuffle 的 time complexity 是 O(n),但不代表一定要 swap 21 億次,在只取前 x 個數的情況下只要 swap x 次,要節約空間可以只儲存前 x 位,後面用 sparse array 表示。
(define
(dealxub
)(let
([table
(make-eqv-hashtable)][deck
(vector
(iota
x))])
(define
(query-bagn)
(if(< nx
)(vector-ref
deckn)
(hashtable-ref
tablenn
)))(
define
(set-bagna
)(if (
< nx
)(vector-set!
deckna
)(hashtable-set!
tablena
)))(
define
(swapab
)(let
([n1
(query-baga)]
[n2(query-bag
b)])
(set-bagan2
)(set-bagbn1
)))(
do ([i0
(1+i
)])((
> ix
))(swapi(
random
ub)))
deck))(
deal
1232100000000)#
(585836641
1704394408
287756151
1094124530
133538688
376300754
1715028628
1321789294
1640809866
1815266134
1488069031
698258677
375271899
1974604429
532481142
563572652
1510250596
1254536230
136859359
560600973
1552934062
1632393768
1065764567
1955170157
183214300
36457973
540184941
1941775863
2035440038
1630151234
1014761669
232402608
210918240
1184108064
1836745758
261190642
38162930
1919453944
506883534
331686386
1275006686
338503303
682230337
190922939
411919935
1181959911
1151088639
1174641970
677781957
1613078407
804055717
1635427601
812613819
949048879
1757720295
72243437
131255810
713392382
224992406
31046706
400480789
456169069
1307296149
1899296034
1951430148
790754379
438428386
1914930139
139797114
762084799
1350608021
494077263
1432774584
1767355978
692191193
2029709387
1852636056
1513288643
577249269
717323121
1942638220
1300355674
672763207
802745663
1553934494
1243642519
1320812869
1381606663
710563182
1760995930
805250428
540672758
1485250105
58068697
1742779026
511176207
2012762061
1754506150
832499524
2098710830
1349631383
407879336
616796009
125646342
766333079
1379023390
304083694
694815780
1470734951
709368736
13485273
145130475
293737784
615168031
1261304392
1479451798
1182073558
603586017
1589492848
1073866299
1647146912
1535357063
231144352
)下一次抽取可以復用 sparse array 中的內容。maphash 把 key 減去己經抽到的數量就行
3樓:
我沒有仔細考證,你可以嘗試.
線性反饋移位暫存器(LFSR)在週期內不重複.
線性同餘(LCG)通過精心選擇引數,也可以在週期內不重複.
如果你不考慮空間複雜度,那麼你可以按順序生成全部21億個數.然後打亂他們就行.
c語言如何生成隨機不重複的幾個數?
涇渭漳淮 如果你只是想獲得幾個或者幾十個隨機數,那最簡單的辦法就OK,拿個陣列把每次產生的隨機數存一下,然後產生新的隨機數之後查詢一下看看是不是重複了就行。如果你想獲得幾k甚至幾兆的隨機數,那查詢就變成了瓶頸,你需要換乙個查詢的方法,紅黑樹字典樹之類的都可以。如果你想獲得幾百兆甚至幾G個不重複的隨機...
Python裡面如何生成隨機數?
Yorlereiyo 9.6.random Generate pseudo random numbers Python 2.7.14rc1 documentation random random Random float x,0.0 x 1.00.37444887175646646 random u...
EXCEL控制合格率生成隨機數?
2018年的問題,當時可能很難實現,但現在可以通過RANDARRAY函式實現了。1 實現效果 演示版本MS EXCEL 365 每次重新整理結果不一致。合格資料為0到10,不合格資料為11到20,可以在公式中調整。2 示例公式 IF ISERROR MATCH COLUMN A F MOD SMAL...