Weighted randomness in Java

2020 Update (interesting how this got 37 upvotes with a glaring bug in the 2011 version below):

• Fix the impossibility to select the last item when Math.random() yields a number very close to 1.0, and we are unlucky with floating point precision: random index -1 would be the result, which is obviously wrong.
• Some code compaction
• Less variable names used

Item[] items = ...;

// Compute the total weight of all items together.
// This can be skipped of course if sum is already 1.
double totalWeight = 0.0;
for (Item i : items) {
    totalWeight += i.getWeight();
}

// Now choose a random item.
int idx = 0;
for (double r = Math.random() * totalWeight; idx < items.length - 1; ++idx) {
    r -= items[idx].getWeight();
    if (r <= 0.0) break;
}
Item myRandomItem = items[idx];

---

2011 version (for comparison left in):

Item[] items = ...;

// Compute the total weight of all items together
double totalWeight = 0.0d;
for (Item i : items)
{
    totalWeight += i.getWeight();
}
// Now choose a random item
int randomIndex = -1;
double random = Math.random() * totalWeight;
for (int i = 0; i < items.length; ++i)
{
    random -= items[i].getWeight();
    if (random <= 0.0d)
    {
        randomIndex = i;
        break;
    }
}
Item myRandomItem = items[randomIndex];

---

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.