创建无重复的随机数序列
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").
相关文章