循环遍历随机排序数组时的概率算法

Question

我认为，通过查看代码，问题非常简单。我有一个随机阵列（数组必须被随机化，一些代码已被排除，因为它不涉及实际问题，但确实需要随机化）。对于数组中的每个元素，都有一个“概率”索引（这里将其描述为值本身，在$rules中），假设提示如果满足其他条件（为了不相关而删除）时，概率数组元素将被“触发”（在这种情况下，该阵列元件的得分将递增1）

考虑代码：

<?php 
    // Taken from php.net/shuffle user notes 
    // Shuffles an array order for the sake of foreach while maintaining 
    // key => value associations 
    function shuffle_assoc(&$array) { 
    $keys = array_keys($array); 
    shuffle($keys); 
    foreach($keys as $key) { 
     $new[$key] = $array[$key]; 
    } 
    return $new; 
    } 

    $i = 1000000; // How many tests to perform 

    // This is my rule list. Each key is a simple color 
    // and each value is a probability represented as a percent 
    $rules = array(
    'black' => 20, 
    'white' => 10, 
    'red' => 40, 
    'green' => 5, 
    'blue' => 25, 
); 

    // Initialize the scores array with all 0's 
    // The "outs" will be used when the probability does not 
    // occur in any of the rules 
    $scores = array('outs' => 0); 
    foreach($rules as $k => $v) { 
    $scores[$k] = 0; 
    } 

    $count = count($rules); 

    for($x = 0; $x < $i; $x++) { 
    $rules = shuffle_assoc($rules); 

    foreach($rules as $k => $probability) { 
     $rand = mt_rand(1,100); 
     //$probability = ??; I've tried applying many different operations here to "correct" the probability 

     if($rand > $probability) { 
     continue; 
     } else { 
     $scores[$k]++; 
     continue 2; 
     } 
    } 
    $scores['outs']++; 
    } 


    foreach($scores as $k => $v) { 
    echo "$k: " . (($v/$i)*100) . "% ($v/$i)\n"; 
    } 

?> 

预期输出（伪）。注意百分比对应与$rules

outs: less than 1% (.../1000000) 
black: 20% (.../1000000) 
white: 10% (.../1000000) 
red: 40% (.../1000000) 
green: 5% (.../1000000) 
blue: 25% (.../1000000) 

例输出值：

outs: 30.7128% (307128/1000000) 
black: 13.2114% (132114/1000000) 
white: 6.3381% (63381/1000000) 
red: 29.5247% (295247/1000000) 
green: 3.1585% (31585/1000000) 
blue: 17.0545% (170545/1000000) 

事情我已经试过&注意事项：

• 正如你所看到的，我环路内有一个$probability = ??的注释部分，我尝试了各种明显的计算每个实际可能性的方法元素，包括玩$count（规则数量），这就是为什么该变量存在和未使用。

• 它不一定非常确切，但最好在较小的一组数字上（e.x. 1,000次迭代）具有稳定的结果。

• 它可能很模糊。 +/- 5％的变化不会伤害我的感觉，特别是在较少的迭代次数中，我理解大数理论在这里起作用。

• 只要它们低于1％-2％，出货次数并不是什么大不了的。我也尝试用各种方法消除缺口，以确定是否单独出现歪斜，有趣的是，当我有一次这样做时，我得到了全部20％的分裂（即使是）。此外，在“出局”时，我能够非常少的出场，通过基本强制性的概率“数字”（也就是，$rules的值）从100开始倒退，能够非常接近正确的分组。 ，但我从来没有找到一个精确的，最佳的方法。每一次，我都会接近一种颜色的结果，这会使其他颜色在小但明显的范围内倾斜。这些数字并没有易于我掌握的相关性，似乎是随机的，尽管很明显结果在概率与大数之间表现良好。

告诉我有一个确切的方法来计算这个。这让我疯狂。

编辑：我有我的代码已敲定的版本，从下面的两个答案的帮助下，做这个工作，而不需要知道概率百分比循环开始前，并没有额外的或嵌套循环（这是我特别需要的，我想我应该在那部分中更直接）。从每个迭代的角度来说，您可以根据该特定迭代的属性动态地提取概率。这里的所有答案都是无价的，这里是我的版本的最终代码：http://pastebin.com/eB3TVP1E

Answer 1

在你的代码中实现杰克的想法（如果概率之和为> 100，这将不起作用）：

php fiddle

<?php 
    // Taken from php.net/shuffle user notes 
    // Shuffles an array order for the sake of foreach while maintaining 
    // key => value associations 
    function shuffle_assoc(&$array) { 
    $keys = array_keys($array); 
    shuffle($keys); 
    foreach($keys as $key) { 
     $new[$key] = $array[$key]; 
    } 
    return $new; 
    } 

    $i = 1000000; // How many tests to perform 

    // This is my rule list. Each key is a simple color 
    // and each value is a probability represented as a percent 
    $rules = array(
    'black' => 20, 
    'white' => 10, 
    'red' => 40, 
    'green' => 5, 
    'blue' => 25, 
); 

    // Initialize the scores array with all 0's 
    // The "outs" will be used when the probability does not 
    // occur in any of the rules 
    $scores = array('outs' => 0); 
    foreach($rules as $k => $v) { 
    $scores[$k] = 0; 
    } 

    $count = count($rules); 
//$limits is what Jack called $rules_norm 
$limits=array(); 
$limit=0; 
foreach($rules as $k=>$v) 
{ 
    $limit+=$v; 
    $limits[$k]=$limit; 
} 
    for($x = 0; $x < $i; $x++) { 
     $rand = mt_rand(1,100); 
foreach($limits as $k=>$v) 
{ 
    if($v>=$rand) 
    { 
     $scores[$k]++; 
     continue(2); 
    } 

} 
    $scores['outs']++; 
    } 


    foreach($scores as $k => $v) { 
    echo "$k: " . (($v/$i)*100) . "% ($v/$i)\n"; 
    } 

?> 

Answer 2

只是规范化结果，积累他们，然后你就完成了。

我的意思是：

• 总和为阵，以获得总的每一个项目提供的所有可能性（这是你的情况100但它很容易一般化）
• 鸿沟每一个概率总

因此，例如：

$rules = array(
    'black' => 20, 
    'white' => 10, 
    'red' => 40, 
    'green' => 5, 
    'blue' => 25, 
); 

将被标准化为：

$rules_norm = array(
    'black' => 0.2, 
    'white' => 0.1, 
    'red' => 0.4, 
    'green' => 0.05, 
    'blue' => 0.25, 
); 

• 现在积累的结果，这样在$rules_norm每个元素你计算所有以前的元素加上当前的总和。

所以：

$rules_norm = array(
    'black' => 0.2, 
    'white' => 0.3, 
    'red' => 0.7, 
    'green' => 0.75, 
    'blue' => 1.0, 
); 

这个

现在你可以只提取范围[0,1)随机浮点数，并选择哪些元素增加根据结果：递增一个元素的成绩从刚开始第一个数组中，并增加了一个，使得$rand > $rules_norm[k]