Simulating weighted random number - Java

Question

I looked at multiple stack overflow articles and couldn't find a reasonable response. If there is a duplicate please indicate.

I have a list of items. Something like:

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

This indicates the possible items this giantRat can drop.

There is a correlated array with matching index that holds what I would hope is the weighted probability of the occurence. Something like:

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

These would be scaled up to say, 50 (multiplied each by 2) and then I would theoretically role a 50 sided dice (Random). This seems like it's been the wrong approach and I can't figure out a way to do this.

Again, the idea is to roll a die and choose 1 item from the list based on weighting. Maybe the dice roll is the wrong way. Any help appreciated.

Answer 1

Great news: I took the non-draconian approach suggested by @pds in the comments section and came up with my own solution. I think @pds solution in the answer section is a more eloquent solution, but here is my own take after studying his and thinking about my problem a little:

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

Answer 2

A simple approach could be as follows. No need to *2, because probabilities will be the same.

    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);

Example at http://ideone.com/xyQlvN

Answer 3

Use Random.nextInt(n), where n is the sum of your weights; then, depending on the interval where the result int drops, you determine the item; e.g. if it is 0 - take the 1st item; if it is between 3 and 8 (inclusively) - take the forth item.

You can easily convert array of weights into array of interval boundaries: just sum all preceding elements. Then, having random int, just go over this interval boundaries array and stop when your random int becomes bigger than the current element of the array.

Because length of the interval is determined by the weights, probability is also determined by it.

Answer 4

One way that you could do it is have each index stored in an array of size 50. So:

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

Then if you like, you can randomly shuffle the array, refer to Random shuffling of an array

Finally, use the random number generator to get the index from that array: double d = 50.0 * Math.random(); String action = giantRat[giantRatDrop[(int)d]];

Answer 5

Simply compute the interval of values that each element has. Let's forget about the multiplication by 2 which doesn't bring anything.

The first element has a weight of 1, so its interval is [0, 1[.

The second one has a weight of 1, so let's start its interval at the value of the previous one, and add 1: [1, 2[.

Same for the third one: [2, 3[.

The 4th one has a weight of 6, so its interval is [3, 9[.

Continue until the end.

Then roll your dice, and find the element which has an interval covering the dice value.