Weighted randomness in Java [duplicate]

Question

This question already has answers here:

Random weighted selection in Java (7 answers)

Closed 2 years ago.

In Java, given n Items, each with weight w, how does one choose a random Item from the collection with a chance equal to w?

Assume each weight is a double from 0.0 to 1.0, and that the weights in the collection sum to 1. Item.getWeight() returns the Item's weight.

Answer 1

TreeMap does already do all the work for you.

Create a TreeMap. Create weights based on your method of choice. Add the weights beginning with 0.0 while adding the weight of the last element to your running weight counter.

i.e. (Scala):

var count = 0.0  
for { object <- MyObjectList } { //Just any iterator over all objects 
  map.insert(count, object) 
  count += object.weight
}

Then you just have to generate rand = new Random(); num = rand.nextDouble() * count to get a valid number.

map.to(num).last  // Scala
map.floorKey(num) // Java

will give you the random weighted item.

For smaller amounts of buckets also possible: Create an array of i.e. 100,000 Int's and distribute the number of the bucket based on the weight across the fields. Then you create a random Integer between 0 and 100,000-1 and you immediately get the bucket-number back.