我想在特定范围内生成随机数，并确保每个新数字都不是以前的重复项。一种解决方案是将以前生成的数字存储在容器中，每个新数字检查容器。如果容器中有这样的数字，则我们再次生成，否则我们使用并将其添加到容器中。但是，随着每个新数字的出现，此操作变得越来越慢。是否有更好的方法或任何可以更快地工作并确保生成独特性的rand函数？
编辑：是的，有一个限制（例如从0到10亿）。但我想生成100,000个唯一数字！（如果解决方案使用Qt功能将非常好。）
如何确保随机生成的数字不会重复？
7
- Narek
5
1如果每个数字都已经生成，你打算做什么？或者你生成的数字数量是固定的吗？ - fredoverflow
同时，https://dev59.com/3nVC5IYBdhLWcg3w4VNy - MSalters
我认为这个问题应该重新开放。10亿是一个非常巨大的数字。通常的生成列表和洗牌方法是不可行的。到目前为止，我还没有看到其他帖子中处理如此巨大数字的适当答案。 - sellibitze
取消之前的翻译。我刚刚添加了一个：https://dev59.com/3nVC5IYBdhLWcg3wvT7g#3094476 - sellibitze
简单地按顺序返回完整的数字范围（例如0-1,000,000,000）。由于这些数字的任何（均匀）随机排列具有相同的出现可能性，因此这个顺序和其他任何顺序一样可能发生。从技术上讲，你无法证明它不是随机的 =p - bta
20个回答
15
这些随机数有范围限制吗？如果你有一个随机数的限制，并且你一直生成唯一的随机数，那么你最终会得到一个 x..y 范围内所有数字的随机排序列表，其中 x-y 是你的随机数的有效范围。如果是这种情况，你可以通过生成 x..y 中所有数字的列表并进行洗牌来大大提高速度，而不是生成数字。
- jkramer
10
我认为根据范围大小和所需的性能模式，有三种可能的方法可以使用另一种算法。
- 创建一个随机数，查看它是否在（排序的）列表中。如果没有则添加并返回，否则尝试另一个。
- 您的列表将随每个所需数字而增长并占用内存。如果每个数字都是32位，则每次都会增加至少32位。
- 每个新的随机数会增加命中率，并使其变慢。
- O(n^2) - 我认为
- 为范围中的每个数字创建一个位数组。如果已返回，则标记为1 / True。
- 现在每个数字只需要1位，如果范围很大，这仍然可能是一个问题，但现在每个数字只分配1位。
- 每个新的随机数会增加命中率，并使其变慢。
- O(n*2)
- 使用所有数字预先填充列表，随机打乱并返回第N个数字。
- 列表不会增长，返回数字不会变慢，
- 但生成列表可能需要很长时间和大量内存。
- O(1)
根据所需速度，您可以将所有列表存储在数据库中。除了速度外，它们无需保存在内存中。
- GvS
8
填写一个数字列表，然后将列表洗牌并从一端选择您需要的数字。
- kasperjj
9
如果他需要32位数字，那么这并不是非常实用的。 - shoosh
无论如何，他需要所有使用数字的索引。 - GvS
5没错，但如果这确实是他的需求，他应该从1开始迭代并接受至少在理论上，这与任何其他顺序一样随机；-) - kasperjj
@shoosh：比特数不重要，数字数才是重要的。（如果我需要5个32位的数字，为什么会有问题？） - sbi
1@kasperjj 直到你说出来，它们才变得随意起来。 - Hernán Eche
显示剩余4条评论
4
如果您使用简单的32位线性同余RNG（例如所谓的"Minimal Standard"），则您只需要存储使用的种子值并将每个生成的数字与其进行比较。如果您再次达到该值，则您的序列开始重复并且您已经用完了所有值。这是O（1），但当然仅限于2 ^ 32-1个值（虽然我认为您也可以使用64位版本）。
- Drew Hall
1
我个人认为这是最好的答案，原因有两点：1）它在时间和空间上是最有效率的；2）它表明解决此问题的方法取决于所使用的随机数生成器函数。 - sashang
3
我认为有一类伪随机数生成器具有您想要的特性：线性同余生成器。如果正确定义，它将产生一个整数列表从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;
}
您需要做的就是选择一个模数，使其大于您在给定运行中所需的数字数量。
- Craig Trader
2
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
- Viktor Sehr
2
如果有这样的模式，那么它就不是随机的了吗？
据我所知，您需要存储并过滤所有不需要的数字...
- FloE
1
如果它们不能重复，它们就不是随机的。
编辑：
此外...
如果它们不能重复，它们就不适合于有限的计算机。
编辑：
此外...
如果它们不能重复，它们就不适合于有限的计算机。
- Hernán Eche
11
2这实际上是不正确的。你可以将“随机”定义为“从不包括最后一个数字的数字集中随机选择”。 - shoosh
7你甚至可以重新定义“重新定义”这个词。 - Hernán Eche
2@Hernán：所以随机性是有限的。但这并不意味着它不再是随机的。您随机数中的位数也会限制它们的随机性。尽管如此，您也不能说它们不是随机的，只是因为您不能拥有超过2^16个数字。 - sbi
1洗一副牌。现在，不看牌，你认为牌堆顶部的牌是随机的吗？底部呢？无疑，两者都是随机的。如果你偷看了顶部的牌，这也不会改变它们的随机性，因为顺序仍然保持不变，依然是随机的。 - MSalters
@jason.rickman：你有注意到你写成了“less random”吗？请看我上面的第一条评论。 - sbi
显示剩余6条评论
1
你可以将数字存储在向量中，并通过索引（1..n-1）获取它们。在每次随机生成后，从向量中删除索引号对应的数字，然后在区间1..n-2中生成下一个数字。以此类推。
- Péter Török
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接