9

I'm having trouble generating random numbers that do not follow a discrete uniform distribution.

So for example, say I have 5 numbers (to keep it simple), a probability of number k being generated would be k/15. (k = 1 to 5)

My idea is to generate a random number j using rand(), and if this number j is:

1 => then number 1 is generated

2 or 3 => num 2

4 or 5 or 6 => num 3

7 or 8 or 9 or 10 => num 4

11 or 12 or 13 or 14 or 15 => num 5

Now scale this to generating 1-10, 1-100, 1-1000. Does this work the way I intend it to? I've constructed a loop that pretty much does this every time a number needs to be generated, I think it's probably inefficient since it goes up until it finds the j number generated in one of the ranges... What could be a better way to do this?

EDIT: or maybe create an array once with the proper numbers and then pull out with rand() better solution?

4

3 回答 3

14

您似乎走在正确的轨道上，但是 C++ 已经为此提供了专门的随机数分布，std::discrete_distribution

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

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());

    // list of probabilities    
    std::vector<double> p = {0, 1.0/15, 2.0/15, 3.0/15, 4.0/15, 5.0/15};
    // could also be min, max, and a generating function (n/15 in your case?)
    std::discrete_distribution<> d(p.begin(), p.end());

    // some statistics
    std::map<int, int> m;
    for(int n=0; n<10000; ++n) {
        ++m[d(gen)];
    }
    for(auto p : m) {
        std::cout << p.first << " generated " << p.second << " times\n";
    }
}

在线演示：http: //ideone.com/jU1ll

于 2012-06-08T02:32:51.030 回答
10

考虑s从 1 到 的整数之和n是s = n * (n + 1) / 2。求解n得到n = (± sqrt(8*s + 1) - 1) / 2。我们可以忽略负平方根，因为我们知道n它是正的。因此n = (sqrt(8*s + 1) - 1) / 2。

因此，插入s1 到 15 之间的整数：

s  n
01 1.000000
02 1.561553
03 2.000000
04 2.372281
05 2.701562
06 3.000000
07 3.274917
08 3.531129
09 3.772002
10 4.000000
11 4.216991
12 4.424429
13 4.623475
14 4.815073
15 5.000000

如果我们取每个计算的上限n（不小于 的最小整数n），我们会得到：

s  n
01 1
02 2
03 2
04 3
05 3
06 3
07 4
08 4
09 4
10 4
11 5
12 5
13 5
14 5
15 5

因此，您可以从均匀分布转到恒定空间和恒定时间的分布（无需迭代，也无需预先计算的表）：

double my_distribution_from_uniform_distribution(double s) {
    return ceil((sqrt(8*s + 1) - 1) / 2);
}

NB 这依赖于sqrt给出一个完美正方形的精确结果（例如，精确地返回 7 给定精确的 49）。这通常是一个安全的假设，因为 IEEE 754 要求平方根的精确舍入。

IEEE 754 双精度可以表示从 1 到 2^53 的所有整数（以及许多更大的整数，但在 2^53 之后不连续）。所以这个函数应该对s从 1 到floor((2^53 - 1) / 8) = 1125899906842623.

于 2012-06-08T02:36:55.620 回答
0

您可以利用奇怪的算术事实：

S(n) = 1 + 2 + 3 + ... + (n - 1) + n

或简化：

S(n) = n * (n + 1) / 2

这使您可以避免存储数组。

于 2012-06-08T02:32:43.337 回答