可能重复： Unique (non-repeating) random numbers in O(1)? How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N
我想在某个diapason中生成随机数，我必须确定，每个新数字都不是前者的副本。一种解决方案是将以前生成的数字存储在容器中，并且每个新数字都检查容器。如果容器中有这样的数字，那么我们生成agin，否则我们使用并将其添加到容器中。但是对于每个新的数字，这个操作变得越来越慢。有没有更好的方法，或任何兰德功能，可以更快地工作，并确保一代的独特性？
编辑：是的，有一个限制（例如从0到1.000.000.000）。但我想生成100.000个唯一数字！ （如果解决方案是使用Qt功能，将会很棒。）
随机数是否有范围？如果您对随机数有限制并且继续生成唯一的随机数，那么您将以随机顺序得到x..y中所有数字的列表，其中x-y是随机数的有效范围。如果是这种情况，您可以通过简单地生成所有数字的列表x..y并对其进行混洗来大大提高速度，而不是生成数字。
你需要多少个随机数？也许你可以将shuffle algorithm应用于预先计算的随机数组？
随机生成器无法根据先前输出的值输出值，因为它们不是随机的。但是，您可以通过使用不同的随机值池来提高性能，每个值都使用不同的盐值组合，这将根据您拥有的池数量来划分数量。
如果随机数的范围无关紧要，您可以使用非常大范围的随机数，并希望您不会发生任何碰撞。如果你的范围是你想要创造的元素数量的数十亿倍，那么碰撞的可能性很小但仍然存在。如果数字不具有实际的随机分布，则可以使用两个部分编号{counter} {random x digits}来确保唯一编号，但不会随机分布。
到目前为止，返回的结果数量不会是O（n ^ 2）的纯函数方法 - 每次生成数字时，您都需要检查到目前为止的每个结果。另外，想想你回来后会发生什么，例如1000中的第1000个数字 - 您将需要平均1000次尝试，直到随机算法出现最后一个未使用的数字，每次尝试需要与已生成的数字进行平均499.5次比较。
从这一点可以清楚地看出，您发布的描述并不完全符合您的要求。正如其他人所说的那样，更好的方法是采用例如提前1000个数字，随机播放，然后逐步从该列表中返回数字。这将保证您不会返回任何重复项，并在初始设置后的O（1）时间内返回数字。
您可以为每个可能的数字为1位数组分配足够的内存。并检查/设置每个生成的数字的位。例如，对于0到65535之间的数字，您只需要8192（8kb）的内存。
这是我提出的一个有趣的解决方案：
假设您有1到1000的数字 - 并且您没有足够的内存。
您可以将所有1000个数字放入一个数组中，然后逐个删除它们，但是会出现内存溢出错误。
您可以将数组拆分为两个，因此您有一个1-500的数组和一个空数组
然后，您可以检查数字1中是否存在该数字，或者第二个数组中是否存在该数字。
因此，假设您有1000个数字，您可以从1-1000获得一个随机数。如果小于500，请检查阵列1并将其删除（如果存在）。如果它不在数组2中，您可以添加它。
这会减少你的内存使用量。
如果使用递归传播它，则可以将500数组拆分为250个空数组。
假设空数组不使用空格，可以减少内存使用量。
搜索速度也会快得多，因为如果你将其分解很多，你会生成一个数字，例如29.它小于500，小于250，小于125，小于62，小于31，大于15，所以你做那6次计算，然后检查包含平均16/2项的数组 - 总共8项。
我应该为这次搜索申请专利，但我敢打赌它已经存在！
特别是给定所需数量的值，您需要一个线性反馈移位寄存器。
为什么？
没有随机的步骤，也不需要跟踪你已经击中的值。只要你的时间少于整个期间，你应该没事。
事实证明，Wikipedia article有一些C ++代码示例，它们比我给你的任何东西都更加经得起考验。请注意，您需要从循环内部提取值 - 循环只是迭代移位寄存器。你可以在代码片段here中看到这个。
（是的，我知道这是在愚蠢的时候提到的 - 在我正在修改的时候看到它。鉴于它没有在这里提出并且是解决海报问题的最佳方式，我认为它应该再次提起。）
假设size = 100.000然后创建一个具有此大小的数组。创建随机数，然后将它们放入array.Problem是该数字的索引？ randomNumber％size将为您提供索引。
当你输入下一个数字时，使用该函数作为索引并检查该值是否存在。如果不存在则将其存在然后创建新数字然后尝试。你可以用这种方式以最快的方式创造。这种方式的失败是你永远不会找到最后一节相同的数字。
例如，最后一节是1231232444556 3458923444556
你的名单上永远不会有这样的数字，即使它们完全不同但最后的部分是相同的。
首先，随机和伪随机之间存在巨大差异。没有任何方法可以从确定性过程（例如计算机）生成完全随机的数字，而无需引入一些物理过程，如击键或其他熵源之间的延迟。
保存所有生成的数字的方法会相当快地减慢计算速度;您拥有的数字越多，您的存储需求就越大，直到您填满所有可用内存。一个更好的方法是（正如某人已经建议的那样）使用众所周知的伪随机数发生器，例如Linear Congruential Generator;它超级快，只需要模块化乘法和加法，其背后的理论在Vol。中得到了很多提及。 Knuth的TAOCP 2。这样，所涉及的理论在重复之前保证了相当长的时间，并且所需的唯一存储是所使用的参数和种子。
如果您可以通过前一个值计算值时没有问题，则LFSR和LCG都可以。如果您不希望另一个输出值可以计算，则可以使用counter mode中的块密码生成输出序列，前提是密码块长度等于输出长度。
我认为有3种可能的方法，取决于范围大小，以及您可以使用其他算法所需的性能模式。
根据所需的速度，您可以将所有列表存储在数据库中。除了速度之外，它们不需要在内存中。
使用Hashset泛型类。此类不包含相同的值。您可以输入所有生成的数字，然后你可以在Hashset中使用它们。你也可以检查它是否存在.Hashset可以以最快的方式确定项目的存在。当列表变大时，哈希集不会变慢，这是最大的特点。
例如 ：
HashSet<int> array = new HashSet<int>();
array.Add(1);
array.Add(2);
array.Add(1);
foreach (var item in array)
{
Console.WriteLine(item);
}
Console.ReadKey();
填写一个包含您需要的号码的列表，然后随机播放列表并从一端选择您的号码。
如果您使用简单的32位线性同余RNG（例如所谓的"Minimal Standard"），您所要做的就是存储您使用的种子值并将每个生成的数字与它进行比较。如果你再次达到这个值，你的序列就会开始重复，你就会失去价值。这是O（1），但当然限于2 ^ 32-1值（虽然我想你也可以使用64位版本）。
我相信有一类伪随机数生成器具有您想要的属性：Linear congruential generator。如果定义正确，它将生成一个从0到N-1的整数列表，在您使用列表中的所有数字之前，没有两个数字重复。
#include <stdint.h>
/*
* Choose these values as follows:
*
* The MODULUS and INCREMENT must be relatively prime.
* The MULTIPLIER-1 must be divisible by all prime factors of the MODULUS.
* The MULTIPLIER-1 must be divisible by 4, if the MODULUS is divisible by 4.
*
* In addition, modulus must be <= 2**32 (0x0000000100000000ULL).
*
* A small example would be 8, 5, 3.
* A larger example would be 256, 129, 251.
* A useful example would be 0x0000000100000000ULL, 1664525, 1013904223.
*/
#define MODULUS (0x0000000100000000ULL)
#define MULTIPLIER (1664525)
#define INCREMENT (1013904223)
static uint64_t seed;
uint32_t lcg( void ) {
uint64_t temp;
temp = seed * MULTIPLIER + INCREMENT; // 64-bit intermediate product
seed = temp % MODULUS; // 32-bit end-result
return (uint32_t) seed;
}
您所要做的就是选择一个MODULUS，使其大于给定运行中您需要的数字。
如果有这样的模式，那不是随机的吗？
据我所知，你必须存储和过滤所有不需要的数字......
unsigned int N = 1000;
vector <unsigned int> vals(N);
for(unsigned int i = 0; i < vals.size(); ++i)
vals[i] = i;
std::random_shuffle(vals.begin(), vals.end());
unsigned int random_number_1 = vals[0];
unsigned int random_number_2 = vals[1];
unsigned int random_number_3 = vals[2];
//etc
您可以将数字存储在矢量中，并通过索引（1..n-1）获取它们。每次随机生成后，从向量中删除索引编号，然后在区间1..n-2中生成下一个编号。等等
如果它们不能重复，它们不是随机的。
编辑：
此外..
如果它们不能重复，它们就不适合有限的计算机