問題描述
O(1) 中的唯一隨機數?
我想要一個偽隨機數生成器，它可以以隨機順序生成沒有重復的數字.
I want an pseudo random number generator that can generate numbers with no repeats in a random order.
例如:
隨機(10)
可能會回來5, 9, 1, 4, 2, 8, 3, 7, 6, 10
might return 5, 9, 1, 4, 2, 8, 3, 7, 6, 10
除了確定數字范圍并將它們改組或檢查生成的列表是否有重復之外，還有什么更好的方法嗎?
Is there a better way to do it other than making the range of numbers and shuffling them about, or checking the generated list for repeats?
此外，我希望它能夠高效地生成沒有整個范圍的大數字.
Also I want it to be efficient in generating big numbers without the entire range.
我看到每個人都在建議 shuffle 算法.但是，如果我想生成大的隨機數(1024 字節+)，那么該方法將比我只使用常規 RNG 并插入到 Set 中直到達到指定長度需要更多的內存，對嗎?有沒有更好的數學算法來解決這個問題.
I see everyone suggesting shuffle algorithms. But if I want to generate large random number (1024 byte+) then that method would take alot more memory than if I just used a regular RNG and inserted into a Set until it was a specified length, right? Is there no better mathematical algorithm for this.
推薦答案
您可能對線性反饋移位寄存器感興趣.我們過去常常用硬件來構建這些，但我也用軟件來完成它們.它使用一個移位寄存器，其中一些位被異或并反饋到輸入，如果您選擇正確的抽頭"，您可以獲得與寄存器大小一樣長的序列.也就是說，一個 16 位的 lfsr 可以產生一個長度為 65535 的沒有重復的序列.它在統計上是隨機的，但當然是可重復的.此外，如果做錯了，你會得到一些令人尷尬的短序列.如果您查找 lfsr，您會找到有關如何正確構造它們的示例(即最大長度").
You may be interested in a linear feedback shift register. We used to build these out of hardware, but I've also done them in software. It uses a shift register with some of the bits xor'ed and fed back to the input, and if you pick just the right "taps" you can get a sequence that's as long as the register size. That is, a 16-bit lfsr can produce a sequence 65535 long with no repeats. It's statistically random but of course eminently repeatable. Also, if it's done wrong, you can get some embarrassingly short sequences. If you look up the lfsr, you will find examples of how to construct them properly (which is to say, "maximal length").
這篇關于創建無重復的隨機數序列的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！