生成随机加权值

因为流感我今天呆在家里:(我决定试着帮你解决这个问题。)。基本上你要求的是某种插值。我用了最简单的(线性的),这些是我的结果和代码。代码有点混乱,我可能会在接下来的几天内修复它。。

<?php

// this function interpolates $a to $b over $steps steps, starting from key $k
// this can be cleaned up significantly
function interpolate($a, $b, $steps, $k) {
    @$per_step = abs($a - $b)/$steps; // suppress warnings in case of division by zero
    if ($a > $b)
        $decreasing = true;
    else
        $decreasing = false;
    $final = array();
    for ($i = 1; $i <= $steps-1; ++$i) {
        if ($decreasing)
            $final[$i+$k] = $a-=$per_step; // linear interpolation
        else
            $final[$i+$k] = $a+=$per_step; // linear interpolation
    }
    return $final;
}

// this function combines probability arrays after the interpolation occurs
// this may happen multiple times, think about 1, 3, 5. interpolation would have to occur
// from 1 -> 2 -> 3, and from 3 -> 4 -> 5.
function interpolateProbabilities ($nodes) {
    $pNodes = array();
    $pNodes = $nodes;
    $keys = array_keys($nodes);
    for ($i = 0; $i < count($keys); $i++) {
        if ($keys[$i+1] - $keys[$i] != 1) {
            $pNodes += interpolate($nodes[$keys[$i]], $nodes[$keys[$i+1]], $keys[$i+1] - $keys[$i], $keys[$i]);
        }
    }
    ksort($pNodes);
    return $pNodes;
}

// this generates a weighed random value and is pretty much copy-pasted from:
// http://w-shadow.com/blog/2008/12/10/fast-weighted-random-choice-in-php/
// it's robust and re-writing it would be somewhat pointless
function generateWeighedRandomValue($nodes) {
    $weights = array_values($nodes);
    $values = array_keys($nodes);
    $count = count($values);
    $i = 0;
    $n = 0;
    $num = mt_rand(0, array_sum($weights));
    while($i < $count) {
        $n += $weights[$i];
        if($n >= $num) {
            break;
           }
        $i++;
       }
    return $values[$i];
}

// two test cases
$nodes = array( 1 => 12, 5 => 22, 9 => 31, 10 => 35); // test 1
$nodes = array( 1 => 22, 3 => 50, 6 => 2, 7 => 16, 10 => 10); // test 2
$export = array();

// run it 1000 times
for ($i = 0; $i < 1000; ++$i) {
    $export[generateWeighedRandomValue(interpolateProbabilities($nodes))]++;
}

// for copy-pasting into excel to test out distribution
print_r($export);

?>

在下列情况下:

$nodes = array( 1 => 12, 5 => 22, 9 => 31, 10 => 35); // test 1

我得到了以下(最终)数组:

Array
(
    [5] => 92
    [7] => 94
    [10] => 162
    [8] => 140
    [3] => 71
    [6] => 114
    [2] => 75
    [4] => 69
    [9] => 131
    [1] => 52
)

1 有12%的时间, 5 22%, 9 10 35%的时间。让我们绘制图表:

看起来很有前途,但让我们试试更疯狂的。。。

$nodes = array( 1 => 22, 3 => 50, 6 => 2, 7 => 16, 10 => 10); // test 2

3 应在50%的时间内发生,并急剧减少到 6 . 让我们看看会发生什么!这是阵列(在回顾中,我应该对这些阵列进行排序):

Array
(
    [4] => 163
    [7] => 64
    [2] => 180
    [10] => 47
    [1] => 115
    [5] => 81
    [3] => 227
    [8] => 57
    [6] => 6
    [9] => 60
)

让我们看看图片:

看起来很管用:)

我希望我能解决你的问题(或者至少给你指出正确的方向)。请注意,我的代码目前有一些规定。也就是说,您提供的初始节点的概率必须达到100%,否则您可能会得到一些不可靠的行为。

另外,代码有点混乱,但概念相对简单。其他一些很酷的东西将是尝试,而不是使用线性插值,使用其他类型,这将给你更有趣的结果!

为了避免混淆,我只展示算法是如何工作的。 我给PHP一个 $node integer => frequency in percentage 最后看起来像 array( 1 => 22, 3 => 50, 6 => 2, 7 => 16, 10 => 10) ,这是 test 2

Test 2 基本上说,您希望将5个控制节点放置在 1, 3, 6, 7, and 10 频率为 22%, 50%, 2%, 16%, and 10% 分别是。首先,我要看清楚 哪里 我需要做插值。例如,我不需要在 6个 和 7 做 1个 三 (我们需要插入 2 7个 和 (我们需要插入 8 和

之间的插值 1 -> 3 有 (3 - 1) - 1 = 1 key[2] 在原始数组中。价值( % )为了 1->3个 abs($a - $b) / $steps 它转化为 % 属于 1个 % 属于 2个 steps + 1 在我们的情况下 14 . 我们需要看看函数是递增还是递减(hello微积分)。如果函数在增加,我们保持 添加 % 到新的插值数组,直到我们填满所有的空点(如果函数减少,我们减去步骤 % value 2 => 36 ( 22 + 14 = 36 ).

(1 => 22, 2 => 36, 3 => 50, 6 => 2, 7 => 16, 10 => 10) . 程序内插 ,这是一个百分比值,我们没有明确声明。

在这种情况下 7 -> 10 ,有两个步骤,步骤百分比为 2个 它来自 (16-10) / (3 + 1) = 2 2个 反复。最后的插值数组是 (8 => 14, 9 => 12)

下图显示绿色(初始值)和红色(插值值)。你可能得“看图像”才能看清楚整件事。你会注意到我用 ± 因为算法需要计算出我们在一段时间内是增加还是减少。

这段代码可能应该用更面向对象的范式编写。我经常玩数组键(例如,我需要通过 $k 所以当我从 interpolate($a, $b, $steps, $k) 因为他们自动拥有正确的钥匙。这只是一个PHP特性,回想起来,我可能应该从一个更可读的OOP方法开始。

这是我最后一次编辑,我保证:)因为我喜欢玩Excel,这显示了数字插值后百分比是如何正常化的。这一点很重要,特别是考虑到在你的第一张照片中,你所展示的是一种数学上的不可能。

Test 1 测试2

在这张图中,我称了一下 1 = > 1, 5 => 98, 10 => 1 你看到了阻尼效应的极端。毕竟,根据定义,百分比必须加起来达到100!重要的是要认识到阻尼效应与两个极端之间的步数成正比。

假设您可以处理百分比的整数,只需将0到99之间的每个值赋给一个结果—例如,0-9的结果可能是1,95-99的结果可能是6(给出10%=1和5%=6的情况)。一旦你得到了这个转换函数(不管你如何实现——你可以使用多种方法),你只需要生成一个0-99范围内的随机数,并将其转换成结果。

你的问题在你想要的代码(甚至是哪种语言-C#或PHP?)方面还不是很清楚但希望这会有帮助。

这里有一些C#代码,可以让你得到任何你喜欢的偏见,在合理的范围内-你不必用百分比来表示,但你可以这样做:

static int BiasedRandom(Random rng, params int[] chances)
{
    int sum = chances.Sum();
    int roll = rng.Next(sum);
    for (int i = 0; i < chances.Length - 1; i++)
    {
        if (roll < chances[i])
        {
            return i;
        }
        roll -= chances[i];
    }
    return chances.Length - 1;
}

例如,你可以使用

int roll = BiasedRandom(rng, 10, 10, 10, 10, 10, 50) + 1;

用C#快速肮脏的方式:

T PickWeightedRandom<T>(IEnumerable<Tuple<T,double>> items, Random r)
{
    var sum = 0.0;
    var rand = r.NextDouble();
    return items.First(x => { sum += x.Item2; return rand < sum; }).Item1;
}

测试代码:

var values = new [] { 
    Tuple.Create(1, 0.05),
    Tuple.Create(2, 0.15),
    Tuple.Create(3, 0.3),
    Tuple.Create(4, 0.3),
    Tuple.Create(5, 0.15),
    Tuple.Create(6, 0.05),
};

const int iterations = 1000;

var counts = new int[values.Length];
var random = new Random();

for (int i = 0; i < iterations; i++)
{
    counts[PickWeightedRandom(values, random)-1]++;
}

foreach (var item in counts)
{
    Console.WriteLine(item/(double)iterations);
}

0.050224
0.150137
0.300592
0.298879
0.150441
0.049727

看起来像:

一种生成非均匀随机数的通用技术 rejection sampling . 即使在这种情况下它可能是无效的,你仍然应该知道如何做到这一点,因为它适用于你提供的任何密度函数。

function random($density, $max) {
    do {
        $rand = lcg_value();
        $rand2 = lcg_value() * $max;
    } while ($density($rand) < $rand2);
    return $rand;
}

$density 这里有一个密度函数,它接受一个介于0和1之间的浮点数作为参数,并返回一个小于 $max

$density = function($x) {
    static $values = array(
        1 => 0.05,
        2 => 0.15,
        3 => 0.30,
        4 => 0.30,
        5 => 0.15,
        6 => 0.05,
    );

    return $values[ceil($x * 6)];
};

一个例子是:

ceil(random($density, 0.3) * 6); // 0.3 is the greatest value returned by $density
// round and * 6 are used to map a 0 - 1 float to a 1 - 6 int.

如果无法轻松计算分布的逆,则拒绝采样特别有用。在这种情况下,使用 inverse transform sampling Jon's answer .

注:以上实现是通用的,因此使用0到1之间的随机值。通过构建一个只适用于您的方法的函数,一切都变得更容易:

function random() {
    static $values = array(
        1 => 0.05,
        2 => 0.15,
        3 => 0.30,
        4 => 0.30,
        5 => 0.15,
        6 => 0.05,
    );

    do {
        $rand = mt_rand(1, 6);
        $rand2 = lcg_value() * 0.3;
    } while ($values[$rand] < $rand2);
    return $rand;
}

random();

重新映射输出分布函数,使其下的区域是统一的,范围从0开始。然后计算它的积分。存储整数(例如,作为值数组)。然后,当您需要一个随机数来匹配轮廓时,首先从内置生成器中获取一个介于0和1之间的随机数,然后在积分上找到Y坐标,其中X坐标是您生成的值。最后,将该值缩放到所需的范围(例如,如果要查找介于0和10之间的值,则乘以10;如果要查找介于-8和+8之间的值,则乘以16并减去8)。

如果随机数生成器没有生成平面轮廓,那么最简单的方法是使用与上述方法相反的方法将其转换为平面轮廓。

我还没试过,但我想这可能管用:

$random($probability)
{
    $rnd = rand() / getrandmax();

    foreach($probability as $num => $prob)
    {
        $rnd -= $prob;
        if($rnd <=0)
            return $num;
    }

    return -1; //this should never happen
}

这样称呼它(使用第二个例子):

$distribution = array(
    1 => 0.10,
    2 => 0.15,
    3 => 0.30,
    4 => 0.27,
    5 => 0.14,
    6 => 0.04);

$number = random($distribution);