模拟加权随机数 - Java

Question

我查看了多篇堆栈溢出文章，但找不到合理的回应。如有重复请注明

我有一个物品清单。类似于：

String giantRat []={"Bandage", "Healing Potion", "Minor Healing Potion", "Rat Teeth", "Fur", "Rat Tail", ""};

这表示此 giantRat 可能掉落的物品。

有一个具有匹配索引的相关数组，其中包含我希望的加权发生概率。类似于：

int giantRatDropRate[]={1,1,1,6,8,3,5};

这些将按比例放大到 50（每个乘以 2），然后理论上我会投掷 50 个面的骰子 (Random)。这似乎是错误的方法，我想不出办法来做到这一点。

同样，我们的想法是掷骰子并根据权重从列表中选择 1 项。也许掷骰子的方式是错误的。任何帮助表示赞赏。

Answer 1

简单地计算每个元素具有的值的区间。让我们忘记乘以 2，它不会带来任何结果。

第一个元素的权重为1，所以它的区间是[0, 1[。

第二个的权重为 1，所以让我们从前一个的值开始它的区间，并加 1：[1, 2[。

第三个也一样：[2, 3[。

第4个权重为6，所以区间为[3, 9[。

继续到最后。

然后掷骰子，找到区间覆盖骰子值的元素。

Answer 2

一种方法是将每个索引存储在一个大小为 50 的数组中。因此：

 int[] giantRatDropRate = new int[50];
 giantRatDropRat = { 0 , 0 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3... };

然后如果你喜欢，可以随机打乱数组，参考Random shuffling of an array

最后，使用随机数生成器从该数组中获取索引：双 d = 50.0 * Math.random(); 字符串动作 = giantRat[giantRatDrop[(int)d]];

Answer 3

使用Random.nextInt(n)，其中n是你的权重之和；然后，根据结果int下降的时间间隔，确定item；例如如果为 0 - 取第一项；如果它在 3 和 8 之间（含）- 取第四项。

您可以轻松地将权重数组转换为区间边界数组：只需对所有前面的元素求和即可。然后，有了随机整数，就遍历这个区间边界数组，当你的随机整数变得大于数组的当前元素时停止。

因为区间的长度是由权重决定的，所以概率也由它决定。

Answer 4

一个简单的方法如下。不需要*2，因为概率是一样的。

    String giantRat []={"Bandage", "Healing Potion", "Minor Healing Potion", "Rat Teeth", "Fur", "Rat Tail", ""};


    int[] a = {1,1,1,6,8,3,5};
    int sum = 0;
    for(int i: a)
       sum += i;
    Random r = new Random();
    int s = r.nextInt(sum);  //Get selection position (not array index)

    //Find position in the array:
    int prev_value = 0;
    int current_max_value = 0;
    int found_index = -1;
    for(int i=0; i< a.length; i++){ //walk through the array
      current_max_value = prev_value + a[i];
      //is between beginning and end of this array index?
      boolean found = (s >= prev_value && s < current_max_value)? true : false;
      if( found ){
        found_index = i;
        break;
      }
      prev_value = current_max_value;
    }

    String selection = "unknown";
    if( found_index != -1 ){
      selection = giantRat[found_index];
    }
    System.out.println(selection);

示例位于 http://ideone.com/xyQlvN

Answer 5

好消息：我采用了@pds 在评论部分建议的非严厉方法，并提出了我自己的解决方案。我认为答案部分的@pds 解决方案是一个更 eloquent 的解决方案，但这是我在研究他的并稍微思考我的问题后自己的看法：

https://gist.github.com/anonymous/f985c1839e5a6be94883

模拟加权随机数 - Java

Simulating weighted random number - Java

java

random

probability