在整个范围内均匀生成随机数

117

我需要在指定的区间[max;min]内生成随机数。

此外,随机数应该在区间上均匀分布,而不是聚集在某个特定点。

目前我正在这样生成:

for(int i=0; i<6; i++)
{
    DWORD random = rand()%(max-min+1) + min;
}

根据我的测试,随机数只在一个点附近生成。

Example
min = 3604607;
max = 7654607;

生成的随机数:

3631594
3609293
3630000
3628441
3636376
3621404

下面的回答中提到:OK,RAND_MAX是32767。我在C++ Windows平台上。是否有其他方法可以生成具有均匀分布的随机数?


4
建造一个“骰子奇妙机器”: http://gamesbyemail.com/News/DiceOMatic - Jarett Millard
1
我不知道C++的rand()是均匀的。你使用的是哪个库?cstdlib.hrand()是不均匀的:http://www.cplusplus.com/reference/cstdlib/rand/ - Mike Warren
3
不,rand() 函数是均匀的(除非在一些早期有缺陷的实现中)。不均匀的是使用模运算符“%”来限制范围。请参考 https://dev59.com/p3A75IYBdhLWcg3w-OZA#2999130 获取正确的解决方案,或者如果您可以使用 'arc4random_uniform',则也可以直接使用它。 - John Meacham
@Alien01:你是否考虑将接受的答案更改为“Shoe”的答案(“为什么rand是一个坏主意”等)?我的答案已经过时,每次我因为它而获得赞时,我感觉有人在错误的通道奔跑。 - peterchen
关于C++11中随机数的白皮书非常不错。 - Pupsik
相关:JavaScript的对应规范问题 - Peter Mortensen
20个回答

220

为什么使用rand是不好的选择

在这里你得到的大部分答案都使用了rand函数和取模运算符。这种方法可能无法均匀地生成数字(这取决于范围和RAND_MAX的值),因此不建议使用。

C++11和范围内的随机数生成

使用C++11,还有多种其他选项可供选择。其中一种非常适合您的要求,可以很好地在范围内生成随机数:std::uniform_int_distribution。以下是一个示例:

#include <iostream>
#include <random>
int main()
{    
    const int range_from  = 0;
    const int range_to    = 1000;
    std::random_device                  rand_dev;
    std::mt19937                        generator(rand_dev());
    std::uniform_int_distribution<int>  distr(range_from, range_to);

    std::cout << distr(generator) << '\n';
}

在Godbolt上在线尝试

这里是运行示例.

模板函数可能会有所帮助:

template<typename T>
T random(T range_from, T range_to) {
    std::random_device                  rand_dev;
    std::mt19937                        generator(rand_dev());
    std::uniform_int_distribution<T>    distr(range_from, range_to);
    return distr(generator);
}

其他随机数生成器

<random> 头文件 提供了无数其他类型的随机数生成器,包括伯努利、泊松和正态分布。

如何对容器进行洗牌?

标准库提供了 std::shuffle 函数,可以按照以下方式使用:

#include <iostream>
#include <random>
#include <vector>
int main()
{    
    std::vector<int> vec = {4, 8, 15, 16, 23, 42};
 
    std::random_device random_dev;
    std::mt19937       generator(random_dev());
 
    std::shuffle(vec.begin(), vec.end(), generator);
    std::for_each(vec.begin(), vec.end(), [](auto i){std::cout << i << '\n';});
}

在Godbolt上在线尝试

该算法会以线性复杂度随机重新排序元素。

Boost.Random

另一种选择是,如果您没有C++11+编译器,可以使用Boost.Random。它的接口与C++11非常相似。


35
请留意这个答案,因为它更加现代化。 - gsamaras
这是正确的答案。谢谢!不过,我想看到更详细的描述,包括代码的每一步。例如,mt19937类型是什么? - Apollo
1
@Shoe,对于给定的范围,它按照相同的顺序生成数字,1 9 6 2 8 7 1 4 7 7。你知道如何在每次运行程序时随机化这些数字吗? - user405398
3
@Richard,有什么替代方案吗? - Shoe
@Shoe:我从标题为“C++11和范围生成”的部分复制了代码,但我的代码似乎抛出了异常。编译器没有抛出任何错误,但运行时却抛出了以下内容:`terminate called after throwing an instance of 'std::runtime_error' what(): random_device::random_device(const std::string&)This application has requested the Runtime to terminate it in an unusual way.它还返回了0x3`。据我所知,我正在使用GNU-GCC编译器,但我对C++还很陌生,不理解发生了什么。 - Mushroom Man
显示剩余5条评论

64

注意:不要在统计、模拟、密码学或其他严肃场合使用rand()

对于一个匆忙的人来说,这足以使数字看起来随机,但不能更多地实现。

请参见Jeffrey的回答以获取更好的选项,或此答案以获得加密安全的随机数。


通常,高位比低位显示更好的分布,因此生成简单用途范围内的随机数的推荐方法是:

((double) rand() / (RAND_MAX+1)) * (max-min+1) + min

注意:确保RAND_MAX+1不会溢出(感谢Demi)!

除法在区间[0, 1)中生成随机数;将其“拉伸”到所需范围。只有当max-min+1接近RAND_MAX时,您需要像Mark Ransom发布的“BigRand()”函数。

这也避免了由于模数引起的一些切片问题,这可能会使您的数字更糟糕。


内置的随机数生成器不能保证具有用于统计模拟所需的质量。对于人类来说,数值“看起来随机”是可以的,但对于严肃的应用程序,您应该采取更好的东西 - 或者至少检查它的属性(均匀分布通常很好,但值倾向于相关,序列是确定性的)。Knuth对随机数发生器有一个优秀的(如果难以阅读)论文,我最近发现LFSR非常棒且易于实现,只要它的属性对您来说是好的。


5
即使所需的数值范围没有超过RAND_MAX,BigRand功能可以提供更好的结果。当RAND_MAX为32767且您需要32767个可能的值时,请考虑这一点-其中32768个随机数字(包括零)中的两个将映射到同一个输出,并且比其他数字出现的概率高出两倍。这几乎不是理想的随机属性! - Mark Ransom
10
(RAND_MAX + 1) 这种写法不太好,可能会导致数值溢出并得到一个负数。更好的做法是:((double)RAND_MAX) + 1.0。请注意,这里只是转述,没有加入任何额外的解释或内容。 - Demi
5
我认为你误解了demi的意思。她的意思是这样的:( rand() / ((double)RAND_MAX+1)) * (max-min+1) + min。只需要将转换为double的操作移到前面,就可以避免问题了。 - Mooing Duck
3
这仅仅将范围内底部的32767个值的分布方式改变为均匀分布在整个范围内的32767个值,并且剩余的4017233个值永远不会被该算法选中。 - Mooing Duck
2
给出的答案有误差,正确的方程式应该是: ((double) rand() / (RAND_MAX+1.0)) * (max-min) + min 当使用%而非*时,要使用“max-min+1”。当您将min=0,max=1时就会看到原因。请peterchen或@peter-mortensen进行修改。 - davepc
显示剩余2条评论

20
我想用一篇简短的综述来补充Shoe'speterchen的出色答案

一些好选择

randutils

randutils(展示)是一个有趣的新奇事物,提供了一个简单的接口和(声明的)强大的随机能力。它的缺点是需要在你的项目中添加依赖,并且由于它是新的,它还没有经过广泛的测试。不管怎样,由于它是免费的(MIT许可证)并且只需要头文件,我认为值得一试。

最小示例:掷骰子

#include <iostream>
#include "randutils.hpp"
int main() {
    randutils::mt19937_rng rng;
    std::cout << rng.uniform(1,6) << "\n";
}

即使一个人对图书馆不感兴趣,该网站也提供了许多有关随机数生成主题和特别是C++库的有趣文章。

Boost.Random

Boost.Random(文档)是启发了C++11<random>库,两者共享很多接口。虽然理论上也是外部依赖,但Boost现在已经成为“准标准”库,其Random模块可以被认为是生成高质量随机数的经典选择。它相对于C++11的解决方案具有两个优点:

  • 更具可移植性,只需要编译器支持C++03
  • random_device使用系统特定方法提供高质量的种子
唯一的小缺陷是提供random_device模块不是头文件,需要编译和链接boost_random

最小示例:掷骰子

#include <iostream>
#include <boost/random.hpp>
#include <boost/nondet_random.hpp>

int main() {
    boost::random::random_device                  rand_dev;
    boost::random::mt19937                        generator(rand_dev());
    boost::random::uniform_int_distribution<>     distr(1, 6);

    std::cout << distr(generator) << '\n';
}

虽然最小样本很好地完成了它的工作,但实际程序应该采用一对改进:
  • mt19937设为thread_local:生成器相当臃肿(超过2KB),最好不要在堆栈上分配
  • 使用多个整数来种子化mt19937Mersenne Twister有一个大状态,在初始化期间可以受益于更多的熵

一些不太好的选择

C++11库

尽管是最惯用的解决方案,但<random>库对于基本需求而言,其接口复杂度远高于所提供的功能。问题在于std::random_device:标准并未规定其输出的最小质量(只要entropy()返回0即可),截至2015年,MinGW(虽然不是最常用的编译器,但也不算是奇特的选择)将始终在最小样本上输出4
最小样本:掷骰子。
#include <iostream>
#include <random>

int main() {
    std::random_device                  rand_dev;
    std::mt19937                        generator(rand_dev());
    std::uniform_int_distribution<int>  distr(1, 6);

    std::cout << distr(generator) << '\n';
}

如果实现不是腐烂的话,这个解决方案应该与 Boost 的解决方案等效,并且同样的建议适用。

Godot 的解决方案

最小示例:掷骰子

#include <iostream>
#include <random>

int main() {
    std::cout << std::randint(1,6);
}

这是一个简单、有效、整洁的解决方案。唯一的缺陷是编译时间会比较长——大约需要两年的时间,前提是C++17能够按时发布,并且实验性的randint函数被批准加入新标准中。也许到那个时候,种子质量的保证也会得到改善。

更糟更好的解决方案

最小样例:掷骰子

#include <cstdlib>
#include <ctime>
#include <iostream>

int main() {
    std::srand(std::time(nullptr));
    std::cout << (std::rand() % 6 + 1);
}

英译中:

旧的 C 语言解决方案被认为是有害的,原因很充分(参见这里的其他答案或这篇详细分析)。然而,它还是有优点的:简单、便携、快速且诚实。从某种意义上说,我们知道获得的随机数质量很差,因此不会被诱惑去将其用于严肃的场合。

会计小恶魔解决方案

最小示例:掷骰子

#include <iostream>

int main() {
    std::cout << 9;   // http://dilbert.com/strip/2001-10-25
}

虽然在普通骰子的投掷中得到9有些不寻常,但人们必须钦佩这个解决方案中优秀特质的完美结合。它是最快速、最简单、最缓存友好和最易移植的方案。将9替换为4,就可以获得适用于任何龙与地下城骰子的完美生成器,同时避免了带有符号的1、2和3。唯一的小缺陷是,由于Dilbert会计巨魔的暴躁情绪,该程序实际上会引发未定义的行为。

1
randutils 库现在被称为 PCG。 - tay10r

10

如果 RAND_MAX 是32767,你可以很容易地将比特数加倍。

int BigRand()
{
    assert(INT_MAX/(RAND_MAX+1) > RAND_MAX);
    return rand() * (RAND_MAX+1) + rand();
}

1
我认为这个不起作用。伪随机数生成器通常是确定性的。例如,如果第一个“rand”调用返回“0x1234”,第二个调用返回“0x5678”,那么你会得到“0x12345678”。这是你可以得到以“0x1234”开头的唯一数字,因为下一个数字总是“0x5678”。你得到32位结果,但你只有32768个可能的数字。 - user694733
1
@user694733 一个好的随机数生成器具有比其可以生成的输出数量更大的周期,因此0x1234不会总是后跟0x5678。 - Mark Ransom
rand()通常不是一个好的随机数生成器。它并没有要求是好的。 - undefined
@TobySpeight 这里有很多答案都提供了rand的替代方案。我的回答是针对你因某种原因而必须使用rand时的情况。 - undefined
我是在回应评论而不是回答本身 - 如果那不清楚的话,对不起。由于rand()的周期没有具体规定,我们无法确定0x1234是否总是会跟随0x5678。我同意在可用的情况下使用<random>更好。 - undefined

8
如果您关心的是随机性而不是速度,那么您应该使用安全的随机数生成方法。有几种方法可以做到这一点...最简单的方法是使用OpenSSL随机数生成器
您还可以编写自己的加密算法(如AES)。通过选择一个种子和一个IV,然后连续重新加密加密函数的输出。使用OpenSSL更容易,但不够男人气。

我不能使用任何第三方库吗?我只能使用C++。 - anand
然后走男人路线,实现AES或其他加密算法。 - SoapBox
2
RC4很容易编写,对于所有实际目的来说足够随机(除了WEP,但这并不完全是RC4的错)。我的意思是,它的代码非常简单。大约20行左右。维基百科条目中有伪代码。 - Steve Jessop
4
为什么不能使用第三方代码?如果这是一道作业题,你应该说明,因为在这种情况下,许多人更愿意给出有用的提示而不是完整的解决方案。如果这不是作业,就去踢说“不允许使用第三方代码”的那个家伙,因为他很愚蠢。 - DevSolar
OpenSSL rand()函数文档的更直接链接:http://www.openssl.org/docs/crypto/rand.html# - DevSolar

8

如果可以的话,使用Boost。我使用他们的随机库运气很好。

uniform_int应该可以满足你的需求。


我对使用Mersenne Twister的uniform_int进行了一些工作,但不幸的是,在某些范围内,uniform_int返回的值并不像我预期的那样均匀。例如,uniform_int<>(0, 3)倾向于产生更多的0,而不是1或2。 - ScaryAardvark
@ScaryAardvark,那听起来像是uniform_int的一个糟糕实现。生成无偏输出非常容易,这里已经有多个问题展示了该方法。 - Mark Ransom
@Mark Ransom。是的,我完全同意。 - ScaryAardvark

5

您需要查看特定编译器/环境下的RAND_MAX

如果rand()生成一个随机的16位数字,您将会看到这些结果。(您似乎假设它将是32位数字)。

我不能保证这是答案,但请发布您的RAND_MAX值和有关您环境的更多详细信息。


3

这应该提供一个在范围[low, high)内的均匀分布,而不使用浮点数,只要总体范围小于RAND_MAX。

uint32_t rand_range_low(uint32_t low, uint32_t high)
{
    uint32_t val;
    // only for 0 < range <= RAND_MAX
    assert(low < high);
    assert(high - low <= RAND_MAX);

    uint32_t range = high-low;
    uint32_t scale = RAND_MAX/range;
    do {
        val = rand();
    } while (val >= scale * range); // since scale is truncated, pick a new val until it's lower than scale*range
    return val/scale + low;
}

如果要处理大于RAND_MAX的值,你需要使用类似如下的方法:

uint32_t rand_range(uint32_t low, uint32_t high)
{
    assert(high>low);
    uint32_t val;
    uint32_t range = high-low;
    if (range < RAND_MAX)
        return rand_range_low(low, high);
    uint32_t scale = range/RAND_MAX;
    do {
        val = rand() + rand_range(0, scale) * RAND_MAX; // scale the initial range in RAND_MAX steps, then add an offset to get a uniform interval
    } while (val >= range);
    return val + low;
}

这大致是std::uniform_int_distribution的工作方式。

3

使用 Mersenne Twister 引擎(C++11):

#include <random>

// Returns a random integer within the range [min, max]
int generateRandomInt(const int min, const int max) {
  static bool is_seeded = false;
  static std::mt19937 generator;

  // Seed once
  if (!is_seeded) {
    std::random_device rd;
    generator.seed(rd());
    is_seeded = true;
  }

  // Use a Mersenne Twister engine to pick a random number
  // within the given range
  std::uniform_int_distribution<int> distribution(min, max);
  return distribution(generator);
}

3

好的,RAND_MAX是32767。 我在C++ Windows平台上。 是否有其他方法可以生成具有均匀分布的随机数? - anand

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接