从一组中获取 X 个唯一的数字
获取我思考的唯一随机数的最优雅的方法是什么？
目前我需要随机的唯一数字，我通过使用 while 循环来检查它是否不唯一，以查看我之前是否使用过该随机数字。
所以看起来：
int n = getRandomNumber % [Array Size];
for each ( Previously used n in list)
Check if I've used n before, if I have...try again.
有很多方法可以解决这个线性 O(n/2) 问题，我只是想知道是否有一种优雅的方法来解决它。试着回想一下 MATH115 离散数学，并记住老讲师是否涵盖了与看似微不足道的问题有关的任何内容。
我现在无法思考，所以也许一旦我喝了一些咖啡因，我的大脑就会因为咖啡引起的智商提高而怀疑它。
What is the most elegant way to grab unique random numbers I ponder?
At the moment I need random unique numbers, I check to see if it's not unique by using a while loop to see if I've used the random number before.
So It looks like:
int n = getRandomNumber % [Array Size];
for each ( Previously used n in list)
Check if I've used n before, if I have...try again.
There are many ways to solve this linear O(n/2) problem, I just wonder if there is a elegant way to solve it. Trying to think back to MATH115 Discrete mathematics and remember if the old lecturer covered anything to do with a seemingly trivial problem.
I can't think at the moment, so maybe once I have some caffeine my brain will suss it with the heightened IQ induced from the Coffee.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果您想要从集合 {1, ..., n} 中无放回地抽取 k 个随机整数（以获得唯一数字），那么您需要的是 [n] 随机排列中的前 k 个元素。生成这种随机排列的最优雅的方法是使用 Knuth shuffle。请参阅此处：http://en.wikipedia.org/wiki/Knuth_shuffle
If you want k random integers drawn without replacement (to get unique numbers) from the set {1, ..., n}, what you want is the first k elements in a random permutation of [n]. The most elegant way to generate such a random permutation is by using the Knuth shuffle. See here: http://en.wikipedia.org/wiki/Knuth_shuffle
2.1 如果 arraySize 为零，则 arraySize = initialArraySize
2.1 生成索引 = getRandomNuber()%arraySize
2.3 结果=数组[索引]。尚未返回结果。
2.2 将 array[index] 与 array[arraySize-1] 交换。 Swap 的意思是“交换” c = array[index];数组[索引] = 数组[数组大小-1];数组[数组大小-1] = c
2.3 将 arraySize 减 1。
2.4 返回结果。
您将获得一个随机数列表，这些随机数在用完唯一值之前不会重复。 O(1) 复杂度。
2.1 if arraySize is zero, then arraySize = initialArraySize
2.1 Generate index = getRandomNuber()%arraySize
2.3 result = array[index]. Do not return result yet.
2.2 swap array[index] with array[arraySize-1]. Swap means "exchange" c = array[index]; array[index] = array[arraySize-1]; array[arraySize-1] = c
2.3 decrease arraySize by 1.
2.4 return result.
You'll get a list of random numbers that won't repeat until you run out of unique values. O(1) complexity.
n 位最大周期线性移位反馈寄存器 (LFSR) 将在内部状态重复之前循环遍历其所有 (2^n -1) 个内部状态。当且仅当由抽头序列加 1 形成的多项式是本原多项式 mod 2 时，LFSR 才是最大周期 LFSR。
因此，n 位最大周期 LFSR 将为您提供 (2^n - 1) 的序列唯一的随机数，每个随机数都是 n 位长。
LFSR 非常优雅。
An n-bit Maximal Period Linear Shift Feedback Register (LFSR) will cycle through all of its (2^n -1) internal states before an internal state is repeated. A LFSR is a Maximal Period LFSR if and only if the polynomial formed from a tap sequence plus 1 is a primitive polynomial mod 2.
Thus, an n-bit Maximal Period LFSR will provide you with a sequence of (2^n - 1) unique random numbers, each one of them is n-bit long.
A LFSR is very elegant.
由于您要强加唯一性，因此伪随机生成器应该足够了，可以将其配置为不重复您可能需要的序列长度。例如，LCG：如果种子是 uint32 并且最初为 0，则使用 (1664525 * 种子) + 1013904223 作为下一个种子，并取低位字作为未重复的 16 位结果。
Since you're imposing uniqueness, then a pseudorandom generator should be sufficient, which can be configured to not repeat for as long a sequence as you probably need. Eg, an LCG: if seed is uint32 and initially 0, then use (1664525 * seed) + 1013904223 for the next seed and take the low word for your unrepeated 16-bit result.