随机基于面积

Question

我有元件的阵列：

$arr = array(
    '0' => 265000, // Area 
    '1' => 190000, 
    '2' => 30000, 
    '3' => 1300 
); 

我想基于该区域（阵列值），以获得随机索引。我需要更频繁地选择大值的区域。 我该怎么做？

我现在拥有的一切：

$random_idx = mt_rand(0, count($arr)-1);  
$selected_area = (object)$arr[$random_idx]; 

谢谢！

Answer 1

1. Repeted值

让我们假设我们具有其中每一个值对应于它的索引的相对概率的阵列。例如，给一枚硬币，折腾的可能结果是50％的尾巴和50％的头部。我们可以代表那些概率的数组，就像（我将使用PHP，因为这似乎是由OP使用的语言）：

$coin = array(  
    'head' => 1,  
    'tails' => 1  
); 

虽然滚动两个骰子的结果可以表示为：

$dice = array('2' => 1, '3' => 2, '4' => 3, '5' => 4, '6' => 5, '7' => 6, 
       '8' => 5, '9' => 4, '10' => 3, '11' => 2, '12' => 1 
); 

一个简单的方法来选择一个概率与这些数组的值成正比（因此与基础模型一致）的随机密钥（索引）是创建另一个数组，其元素是原始数据的密钥重复多次如值所示，然后返回一个随机值。例如，对于dice阵列：

$arr = array(2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, ... 

这样做，我们有信心，每个按键都会有正确的相对概率有所回升。我们可以封装所有逻辑与它建立辅助阵列的返回使用mt_rand()随机索引的功能的建筑工类：

class RandomKeyMultiple { 
    private $pool = array(); 
    private $max_range; 

    function __construct($source) { 
     // build the look-up array 
     foreach ($source as $key => $value) { 
      for ($i = 0; $i < $value; $i++) { 
       $this->pool[] = $key; 
      } 
     } 
     $this->max_range = count($this->pool) - 1; 
    } 

    function get_random_key() { 
     $x = mt_rand(0, $this->max_range); 

     return $this->pool[$x];  
    } 
} 

的使用简单，只是创建该类的一个对象使所述源数组，然后该函数的每个调用将返回一个随机密钥：

$test = new RandomKeyMultiple($dice); 
echo $test->get_random_key(); 

的问题是，OP的数组包含大值，这导致了非常大的（但仍在可控范围内，即使没有除以100的所有值）数组。

2.步骤

通常，离散概率分布可以是更复杂的，条件是不能在重复数很容易地转换的浮点值。

另一种方式来解决这个问题是要考虑数组作为间隔的是把所有可能的值的全球范围内的misures中的值：

+---------------------------+-----------------+-------+----+ 
    |       |     |  | | 
    |<---  265000  --->|<-- 190000 -->|<30000>|1300| 
    |<-------   455000   ------>|   | 
    |<----------    485000   --------->| | 
    |<----------------   486300  -------------->| 

然后，我们可以选择0到1之间的随机数486300（全球范围）并查找正确的指数（其可能性与其段的长度成正比，给出正确的概率分布）。类似：

$x = mt_rand(0, 486300); 
if ($x < 265000) 
    return 0; 
elseif ($x < 455000) 
    return 1; 
elseif ($x < 485000) 
    return 2; 
else 
    return 3; 

我们可以概括该算法并封装在一个类中的所有逻辑（使用辅助数组来存储中的部分和）：

class RandomKey { 
    private $steps = array(); 
    private $last_key; 
    private $max_range; 

    function __construct($source) { 
     // sort in ascending order to partially avoid numerical issues 
     asort($source); 

     // calculate the partial sums. Considering OP's array: 
     // 
     // 1300 ---->  0 
     // 30000 ----> 1300 
     // 190000 ----> 31300 
     // 265000 ----> 221300 endind with $partial = 486300 
     // 
     $partial = 0; 
     $temp = 0; 
     foreach ($source as $k => &$v) { 
      $temp = $v; 
      $v = $partial; 
      $partial += $temp; 
     } 

     // scale the steps to cover the entire mt_rand() range 
     $factor = mt_getrandmax()/$partial; 
     foreach ($source as $k => &$v) { 
      $v *= $factor; 
     } 

     // Having the most probably outcomes first, minimizes the look-up of 
     // the correct index 
     $this->steps = array_reverse($source); 

     // remove last element (don't needed during checks) but save the key 
     end($this->steps); 
     $this->last_key = key($this->steps); 
     array_pop($this->steps); 
    } 

    function get_random_key() { 
     $x = mt_rand(); 

     foreach ($this->steps as $key => $value) { 
      if ($x > $value) { 
       return $key; 
      } 
     } 
     return $this->last_key;  
    } 

} 

Here或here有现场演示用一些例子和帮助函数来检查密钥的概率分布。

对于较大的阵列，也可以考虑查找索引的二进制搜索。

Answer 2

此解决方案基于元素索引，而不是其值。所以我们需要对数组进行排序，以便始终确保具有较大值的元素具有较大的索引。

随机指数发电机现在可以表示为线性关系x = y：

(y) 

a i  4    + 
r n  3   + 
r d  2  + 
a e  1 + 
y x  0 + 
      0 1 2 3 4  

      r a n d o m 
      n u m b e r (x) 

我们需要生成指数非线性（大指标 - 更多概率）：

a i  4        + + + + + 
r n  3     + + + + 
r d  2   + + + 
a e  1 + + 
y x  0 + 
      0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 

      r a n d o m 
      n u m b e r 

为了找到范围为x数值为一个长度为c的数组我们可以计算出所有数字在范围内的总和0..c：

(c * (c + 1))/2; 

要找到x任何y让我们来解决二次方程

y^2 + y - 2 * x = 0; 

已经解决了这一点，我们得到

y = (sqrt(8 * x + 1) - 1)/2; 

现在，让我们把它放在一起：

$c = $count($arr); 
$range = ($c * ($c + 1))/2; 
$random_x = mt_rand(0, range); 
$random_idx = floor((sqrt(8 * $random_x + 1) - 1)/2); 

该解决方案在性能方面最适合大数组 - 它d oes不依赖于数组的大小和类型。

Answer 3

你的数组描述了离散概率分布。每个数组值（“区域”或“权重”）与离散随机变量从数组键的范围中取特定值的概率有关。

/** 
* Draw a pseudorandom sample from the given discrete probability distribution. 
* The input array values will be normalized and do not have to sum up to one. 
* 
* @param array $arr Array of samples => discrete probabilities (weights). 
* @return sample 
*/ 
function draw_discrete_sample($arr) { 
    $rand = mt_rand(0, array_sum($arr) - 1); 
    foreach ($arr as $key => $weight) { 
     if (($rand -= $weight) < 0) return $key; 
    } 
} 

，如果你想支持非整数权重/概率与$rand = mt_rand()/mt_getrandmax() * array_sum($arr);替换第一线。您可能还想看看类似的问题asked here。如果您只想抽取一小部分已知分布，我建议使用分析方法outlined by Oleg Mikhailov。

Answer 4

这个问题有点类似于操作系统可以识别下一个线程与lottery scheduling运行的方式。

这个想法是根据每个区域的大小和数量为每个区域分配所有这些票据。根据选择哪一个随机数，你知道哪张票赢了，因此胜出的区域。

首先，您需要总结所有区域，然后找到一个总数达到此数的随机数。现在，您只需遍历数组，并查找总计到此点的第一个元素大于随机数。

假设你正在寻找在PHP的解决方案：

function get_random_index($array) { 
    // generate total 
    $total = array_sum($array); 
    // get a random number in the required range 
    $random_number = rand(0, $total-1); 
    // temporary sum needed to find the 'winning' area 
    $temp_total = 0; 
    // this variable helps us identify the winning area 
    $current_area_index = 0; 

    foreach ($array as $area) { 
     // add the area to our temporary total 
     $temp_total = $temp_total + $area; 

     // check if we already have the right ticket 
     if($temp_total > $random) { 
      return $current_area_index; 
     } 
     else { 
      // this area didn't win, so check the next one 
      $current_area_index++; 
     } 
    } 
}