Weighted randomness in Java [duplicate]

Question

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

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

---