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

Question

我认为,通过查看代码,问题非常简单.我有一个随机数组(数组必须随机化,一些代码已被排除,因为它不涉及实际问题,但需要随机化).对于数组中的每个元素,都有一个"概率"索引(此处描述为值本身,in $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(规则的数量)这就是为什么变量存在且未使用.

• 它不一定非常精确,但最好在较小的数字集合(前1000次迭代)上具有稳定的结果.

• 它可能非常模糊.+/- 5%的方差不会伤害我的感受,特别是在较少的迭代次数中,我理解大数理论在这里发挥作用.

• 只要它们低于1%-2%,出局次数就不算大.我也尝试使用各种方法消除掉出来,看看是否单独出局,有趣的是当我有一次这样做时,我得到了20%的分裂(即使是偶数).

• 此外,在"出局",我能够非常接近正确的分裂,基本上是粗暴的 - 强迫概率"数字"(即值$rules)从100开始,但我从未能够找出一种精确,最佳的方法.每一次,我都会接近一种颜色的结果,这会使其他颜色在一个小而明显的尺度上倾斜.在这些数字中没有易于理解的相关性,并且看起来是随机的,尽管很明显结果与概率和大数字一致.

告诉我有一个精确的计算方法.这让我疯了.

编辑:我有一个我的代码的最终版本,在下面两个答案的帮助下,这样做无需在循环开始之前知道概率百分比,并且没有额外的或嵌套的循环(这是我特别需要的,我猜测我应该在那个部分更直接)..在每个迭代的意义上,你可以根据特定迭代的属性动态地提取概率..这里的所有答案都是无价的,这是我最终代码的版本:http://pastebin.com/eB3TVP1E

Answer 1

杰克的想法在你的代码中实现（如果概率之和>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";
  }

?>