Objective-C中的非均匀随机数

// min value w/ p = 0.7
// some intermediate value w/ p = 0.2
// max value w/ p = 0.1
NSUInteger r = arc4random_uniform(10);
if (r <= 6) 
    result = 0;
else if (r <= 8)
    result = (n - 1) / 2;
else
    result = n - 1;

我认为你基本上是正确的轨道.有可能存在精度或范围问题,但一般情况下如果你想随机选择,比如说3,2,1或0,你想要选择3的概率是选择0的概率的4倍然后是你可能会在一个充满：

3 3 3 3
2 2 2
1 1
0

把东西扔到上面,读出它落下的数字.

您所需线性比例的选项数量为：

- 1 if number of options,n,= 1
- 1 + 2 if n = 2
- 1 + 2 + 3 if n = 3
- ... etc ...

这是算术级数的简单总和.你最终得到n(n 1)/ 2个可能的结果.例如.对于n = 1,其为1 * 2/2 = 1.对于n = 2,其为2 * 3/2 = 3.对于n = 3,则为3 * 4/2 = 6.

所以你会马上写下这样的东西：

NSUInteger random_linear(NSUInteger range)
{
    NSUInteger numberOfOptions = (range * (range + 1)) / 2;
    NSUInteger uniformRandom = arc4random_uniform(numberOfOptions);

    ... something ...
}

那时你只需要决定uniform uniformRandom落入哪个bin.最简单的方法是使用最明显的循环：

NSUInteger random_linear(NSUInteger range)
{
    NSUInteger numberOfOptions = (range * (range + 1)) / 2;
    NSUInteger uniformRandom = arc4random_uniform(numberOfOptions);

    NSUInteger index = 0;
    NSUInteger optionsToDate = 0;
    while(1)
    {
        if(optionsToDate >= uniformRandom) return index;
        index++;
        optionsToDate += index;
    }
}

鉴于您可以在不进行迭代的情况下计算出optionsToDate,一个明显更快的解决方案是二进制搜索.

更明智的方法是uniformRandom是从(0,0)到(n,n)的线下面的框的总和.所以它是图表下方的区域,图形是一个简单的直角三角形.所以你可以从区域公式向后工作.

具体地,图中从(0,0)到位置x的(n,n)的区域是(x * x)/ 2.所以你正在寻找x,其中：

(x-1)*(x-1)/2 <= uniformRandom < x*x/2

=> (x-1)*(x-1) <= uniformRandom*2 < x*x
=> x-1 <= sqrt(uniformRandom*2) < x

在这种情况下,你想要取x-1,因为结果没有进展到数字网格的下一个离散列.所以你可以用平方根操作简单整数截断到达那里.

所以,假设我没有弄清楚我在路上的确切不等式,并假设所有精度都适合：

NSUInteger random_linear(NSUInteger range)
{
    NSUInteger numberOfOptions = (range * (range + 1)) / 2;
    NSUInteger uniformRandom = arc4random_uniform(numberOfOptions);

    return (NSUInteger)sqrtf((float)uniformRandom * 2.0f);
}