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

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 （规则计数）进行调整，这也是该变量存在且未使用的原因。

• 显然不必精确，但最好在较少的数字集合（例如1,000次迭代）中具有稳定的结果。

• 可以相当模糊。误差在+/-5%范围内不会让我感到难受，特别是在较少的迭代次数中，我理解在这里大数理论起着作用。

• 外部数量并不重要，只要它们小于1%-2%即可。我还尝试使用各种方法消除外部因素，以查看外部因素是否单独扭曲，有趣的是，当我做到这一点时，有一个20%的均匀分布（即完全平均）。

• 此外，在“外部”方面，我能够通过从100开始暴力强制执行概率“数字”（即$rules 的值）向后推导得出非常接近正确分裂，但我从未能找到精确的、最优的方法。每次，我都会接近一种颜色的结果，这会在一个小但明显的范围内扭曲其他颜色。这些数字之间没有易于理解的相关性，看起来是随机的，尽管结果与概率与大数理论相吻合。

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

编辑： 我有了一个最终版本的代码，在下面两个答案的帮助下，不需要在循环开始之前知道概率百分比，并且没有额外或嵌套的循环（这正是我需要的，我想我在那部分应该更直接）.. 在每次迭代中，可以基于该特定迭代的属性动态地提取概率.. 所有答案在这里都是无价值的，这是我的最终代码版本: http://pastebin.com/eB3TVP1E

- A.B. Carroll

---

惊喜的是，有人在发问题前进行了调研。我很喜欢你。 - David Harris

所以你只需要正确的概率吗？还是我漏掉了什么？我之前也曾遇到过类似的问题。 - David Harris

为什么要洗牌键？为什么每个键都要生成一个随机数？你复杂化了算法。只需要为每个索引选择一个1到100的随机数，然后找出应该适用的规则，即0-19是黑色，20-29是白色，30-69是红色，70-74是绿色，75-99是蓝色。 - mellamokb

我考虑了你提到的类似于插槽的设置（0-19黑色，20-29白色等），但问题在于这里没有提到其他可能排除白色的条件，例如不相关的条件。这意味着如果随机数落在23上，我们就没有结果了。 - A.B. Carroll

我已经为您的当前代码计算了百分比，它们大致与您得到的相同。问题在于，因为您正在洗牌键并为每个键生成一个随机数，所以您正在使键的连续条目依赖于前面的条目是否恰好匹配“rand”，而选择特定键应该是独立事件。唯一的方法是在主循环的每次迭代中计算所有规则中的正确归一化概率。 - mellamokb

Answer 1

只需将结果标准化、累加，然后您就完成了。

我的意思是：

• 对于数组中的每个项目，给定所有概率之和以获得总和（在您的情况下为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]。

- Jack

Answer 2

下面是将Jack的思路融入您的代码中（如果概率总和>100，则无法工作）:

php代码

<?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";
  }

?>

- Jon Hulka

---

这个完美地运作了。我无法让杰克的想法起作用，因为我仍然在每个foreach中生成随机数，而不是在每次迭代（for）中生成随机数，这使得它的行为非常不同，我甚至不想开始尝试理解。我想补充说明的是，当概率之和大于100%时，这可能会表现出奇怪的行为，但当概率低于100%时，缺失的概率会转移到“outs”，这在我的特定情况下实际上非常有用。 - A.B. Carroll