11

I have an array of doubles and I want to select a value from it with the probability of each value being selected being inversely proportional to its value. For example:

arr[0] = 100
arr[1] = 200

In this example, element 0 would have a 66% of being selected and element 1 a 33% chance. I am having difficulty coding this. What I have done so far is to calculate the total value of the array (the example would be 300), then I've played around with inversing the numbers before calculating them as a percentage of the total. I can't get anything to work. In the end I desire:

new randomNumber
for(int y=0; y < probabilities.length; y++){
     if(randomNumber < probabilities[y]){
          Select probabilities[y]
     }
}

Or something to that affect. Any help? Coding is in Java but I can adapt any pseudocode.

4

4 回答 4

19

通常的技术是将数组转换为累积和数组：

 [10 60 5 25]  --> [10 70 75 100]

在从零到累计总数的范围内选择一个随机数（在示例中：0 <= x < 100）。然后，在累积数组上使用二分法将索引定位到原始数组中：

Random variable x      Index in the Cumulative Array      Value in Original Array
-----------------      -----------------------------      ----------------------
 0 <= x < 10                      0                            10
10 <= x < 70                      1                            60
70 <= x < 75                      2                             5
75 <= x < 100                     3                            25

例如，如果随机变量x为 4，则将累积数组二等分给出位置索引 0，对应于原始数组中的 10。

并且，如果随机变量x为 72，则将累积数组二等分给出位置索引 2，对应于原始数组中的 5。

对于反比例，该技术完全相同，只是您将数组初始转换为其倒数，然后构建累积和数组：

[10 60 5 25]  -->  [1/10  1/60  1/5  1/25]  -->  [1/10  7/60  19/60  107/300]
于 2013-05-10T20:26:32.033 回答
1

对于反比例：

  1. 对数组求和
  2. 选择一个介于 0 和 (n-1)*sum -1 之间的随机数
  3. 从头开始累积总和值，直到您 >= 到随机值。

这是为了比例

注意：所有值都必须为正才能使其正常工作。

  1. 对数组求和
  2. 在 0 和 sum-1 之间选择一个随机数
  3. 累积从数组开头开始的值，直到您 >= 到随机值。
于 2013-05-10T19:33:14.670 回答
1

php代码：

/**
 * Returns a random item from an array based on a weighted value.
 * @param array $array ['foo' => 70, 'bar' => 30] Foo has a 70 percent chance of being returned
 * @return int|string
 */
public function randomize(array $array)
{
    $sumOfWeights = array_sum($array);

    $random = rand(1, $sumOfWeights);
    foreach ($array as $name => $weight) {
        $random -= $weight;

        if ($random <= 0) {
            return $name;
        }
    }

}

求数组中所有元素的总和。然后在这个范围内生成一个随机数。最终选择将是上述函数返回的索引中的元素。

于 2017-03-17T10:50:04.470 回答
0

我遇到了同样的问题并提出了一些简单的解决方案。不是完美的，但适用于某些情况。

您有一些数字 [1,2,3,...] 的数组，您需要选择一个具有一定概率 [10,5,20,...] 的值，只需创建新数组并重复每个值尽可能多的次数它有很大的可能性，例如

arr[] = [1,1,1,1,...(10 times),2,2,2,..(5 times),3,3,3,3,...(20 times)];

他们只是得到从 0 到新数组长度的随机数，并以期望的概率得到你的值。

int r = Random(0,arr.count);
int value = arr[r];

正如我提到的，它并不完美，也不是内存高效算法，但它确实有效。

于 2017-09-19T19:40:50.377 回答