c++ 生成随机布尔值

7lrncoxx  于 2023-05-24  发布在  其他
关注(0)|答案(6)|浏览(232)

我目前正在用C++实现Eller's Algorithm,有一个小细节困扰着我,那就是迷宫的随机性。
到目前为止,我使用以下代码生成一个随机bool

bool randomBool()
{
    return 0 + (rand() % (1 - 0 + 1)) == 1;
}

// In main.cpp

time_t seconds;
time(&seconds);
srand((unsigned int) seconds);

但在调试时,我经常看到重复的truefalse生成,有时一行多达30次。
这个算法真的是随机的吗?或者在C++中有更好的方法吗?

sc4hvdpw

sc4hvdpw1#

C++11中的STL内置了上级rand()的随机数生成方法。你可以通过一个0或1的随机整数来模拟一个随机布尔值:

#include <iostream>
#include <random>

int main(int argc, char *argv[]) {
    auto gen = std::bind(std::uniform_int_distribution<>(0,1),std::default_random_engine());
    const unsigned int N = 100;
    unsigned int numTrue = 0;
    unsigned int numFalse = 0;
    for (int i = 0; i < 100; ++i) {
        bool b = gen();
        if (b) ++ numTrue;
        else ++numFalse;
    }
    std::cout << numTrue << " TRUE, " << numFalse << " FALSE" << std::endl;
}

您可以在标准C++参考中找到有关此库的更多详细信息。例如,如果你想要的不是50/50的“真”和“假”值的比例,你可以创建一个0和1之间的随机浮点数,并调用小于某个阈值z的值为true,否则为false。

为什么你看到长长的条纹,我想

我还没有说明为什么你的代码会连续得到30个“true”或“false”值。虽然rand()不应该再被使用,而且你的代码中似乎有一些不必要的1和0的加减,但不应该有这样的问题。然而,我现在意识到你的问题中的文本是模糊的。如果您连续运行并退出程序30次,您应该会看到重复的值--即使是我的代码。大多数随机数生成器实际上是伪随机数生成器。每次你运行程序,它们都会产生 * 相同 * 的随机数序列;这对于结果的一致性是重要的。然而,当程序运行时(例如,将randomBool()放入一个循环中),您不应该看到这样长度的条纹,因为它们是极不可能的。

不可能出现长条纹

我很惊讶地收到不同意我的Assert的评论,即连续30个“真”或“假”随机布尔值是不可能的(当真或假的可能性相等时)。我意识到,对概率的一个常见误解是,“运气”试图使事情变得均匀,因此,如果抛硬币连续几次出现正面,那么宇宙将试图纠正这一点,使反面更有可能。由于这种误解,人们低估了得到所有正面和所有反面条纹的可能性,我认为对这个答案和主要问题的评论的动机是纠正这个常见的错误。
然而,有一个真实的的原因,长条纹(特别是长达30)越来越不可能。使用随机无偏抛硬币的语言,每个IID(独立同分布)抛硬币只有50%的机会与前一个相同。因此,长条纹的概率随着条纹的长度呈指数下降。对于长度为L的条纹,所有头的条纹的概率为1/2^L;任一类型的条纹的概率为2/2 ^L或1/2^(L-1)。下面是一些要演示的代码:

#include <iostream>
#include <random>
#include <map>

bool randomBool() {
    static auto gen = std::bind(std::uniform_int_distribution<>(0,1),std::default_random_engine());
    return gen();
}

int main(int argc, char *argv[]) {

    const unsigned int N = 1e8;
    std::map<unsigned int,unsigned int> histogram;
    bool current = randomBool();
    unsigned int currentLength = 1;
    for (int i = 0; i < N; ++i) {
        bool b = randomBool();
        if (b == current) {
            ++currentLength;
        } else {
            auto it = histogram.find(currentLength);
            if (it != histogram.end())
                it->second += 1;
            else
                histogram.insert(std::make_pair(currentLength,1));
            currentLength = 1;
        }
        current = b;
    }

    for (auto pair : histogram) 
        std::cout << "STREAK LENGTH " << pair.first << " OCCURS " << pair.second << " TIMES" << std::endl;
}

输出直方图为:

STREAK LENGTH 1 OCCURS 25011106 TIMES
STREAK LENGTH 2 OCCURS 12503578 TIMES
STREAK LENGTH 3 OCCURS 6249056 TIMES
STREAK LENGTH 4 OCCURS 3125508 TIMES
STREAK LENGTH 5 OCCURS 1560812 TIMES
STREAK LENGTH 6 OCCURS 781206 TIMES
STREAK LENGTH 7 OCCURS 390143 TIMES
STREAK LENGTH 8 OCCURS 194748 TIMES
STREAK LENGTH 9 OCCURS 97816 TIMES
STREAK LENGTH 10 OCCURS 48685 TIMES
STREAK LENGTH 11 OCCURS 24327 TIMES
STREAK LENGTH 12 OCCURS 12176 TIMES
STREAK LENGTH 13 OCCURS 6149 TIMES
STREAK LENGTH 14 OCCURS 3028 TIMES
STREAK LENGTH 15 OCCURS 1489 TIMES
STREAK LENGTH 16 OCCURS 811 TIMES
STREAK LENGTH 17 OCCURS 383 TIMES
STREAK LENGTH 18 OCCURS 193 TIMES
STREAK LENGTH 19 OCCURS 104 TIMES
STREAK LENGTH 20 OCCURS 43 TIMES
STREAK LENGTH 21 OCCURS 20 TIMES
STREAK LENGTH 22 OCCURS 14 TIMES
STREAK LENGTH 23 OCCURS 4 TIMES
STREAK LENGTH 24 OCCURS 3 TIMES

难以计算在多个翻转N中长度为L的条纹的预期数量,因为存在许多长度为L的重叠延伸,其中可能存在这样的条纹。然而,请注意,该直方图大致遵循指数分布,每个条目大约是前一条目的一半。
最大条纹为24 [注:上一版本中的一个错误将此计数为23]。在任意一串24次独立掷硬币的串中,出现这种长度的连续掷硬币的概率是1/2^(24-1),或者说大约是1/800万。由于在1 e8次投掷中,大约有1 e8/24 ~ 430万次这样的独立延伸,我们预计会有少量这样的条纹,所以这似乎是正确的[我上面的警告是计算精确的期望值是困难的]。与此同时,在任何30次翻转的独立延伸中,长度为30的连续概率为5.37亿分之一,甚至比长度为24的连续概率要小得多。

e7arh2l6

e7arh2l62#

bool randomBool() {
    return 0 + (rand() % (1 - 0 + 1)) == 1;
}

这可能是将rand()的输出转换为布尔值的最糟糕的方法。在许多实现中,较低阶位比较高阶位随机性小得多。
理想情况下,您可以完全使用其他东西,但如果您必须使用rand(),请尝试:

bool randomBool() {
   return rand() > (RAND_MAX / 2);
}
csga3l58

csga3l583#

下面是一个C++11函数模板,它以指定的概率生成布尔结果(二项分布)(默认0.5表示均匀):

#include <random>
template <typename Prob = double>
bool binomial_trial(const Prob p = 0.5) {
    static auto dev = std::random_device();
    static auto gen = std::mt19937{dev()};
    static auto dist = std::uniform_real_distribution<Prob>(0,1);
    return (dist(gen) < p);
}
bd1hkmkf

bd1hkmkf4#

伪随机数生成器的较低阶位倾向于提供较少的随机性。对于内置的rand()函数尤其如此,它通常被实现为LCG。生成随机bool的最佳方法是使用MSB位。这实际上是标准的Bernoulli distribution,概率为1/2

#include <cmath>
#include <cstdlib>

inline bool random_bool()
{
   static const int shift = static_cast<int>(std::log2(RAND_MAX));
   return (rand() >> shift) & 1;
}
e0uiprwp

e0uiprwp5#

如果rand()是真正的伪随机,则它是真正的伪随机,尽管如果RAND_MAX是偶数(即偶数比奇数多一个),则分布可能非常轻微地不均匀。但通常RAND_MAX足够大,可以忽略差异。

yi0zb3m4

yi0zb3m46#

在现代C++中,有一种专门的方法来生成随机布尔值-通过伯努利分布:

#include <random>

bool randomBoolean() {
  static std::default_random_engine generator(std::random_device{}());
  // With p = 0.5 you get equal probability for true and false
  static std::bernoulli_distribution distribution(0.5);
  return distribution(generator);
}

详情请参见here

相关问题