Random weighted selection in Java

Question

I want to choose a random item from a set, but the chance of choosing any item should be proportional to the associated weight

Example inputs:

item                weight
----                ------
sword of misery         10
shield of happy          5
potion of dying          6
triple-edged sword       1

So, if I have 4 possible items, the chance of getting any one item without weights would be 1 in 4.

In this case, a user should be 10 times more likely to get the sword of misery than the triple-edged sword.

How do I make a weighted random selection in Java?

user_8761198 · Answer

139

There is a straightforward algorithm for picking an item at random, where items have individual weights:

calculate the sum of all the weights
pick a random number that is 0 or greater and is less than the sum of the weights
go through the items one at a time, subtracting their weight from your random number until you get the item where the random number is less than that item's weight

user_15045764 · Answer

A simple (even naive?), but (as I believe) straightforward method:

/**
* Draws an integer between a given range (excluding the upper limit).
* 
* Simulates Python's randint method.
* 
* @param min: the smallest value to be drawed.
* @param max: the biggest value to be drawed.
* @return The value drawn.
*/
public static int randomInt(int min, int max)
    {return (int) (min + Math.random()*max);}

/**
 * Tests wether a given matrix has all its inner vectors
 * has the same passed and expected lenght.
 * @param matrix: the matrix from which the vectors length will be measured.
 * @param expectedLenght: the length each vector should have.
 * @return false if at least one vector has a different length.
 */
public static boolean haveAllVectorsEqualLength(int[][] matrix, int expectedLenght){
    for(int[] vector: matrix){if (vector.length != expectedLenght) {return false;}}
    return true;
}

/**
* Draws an integer between a given range
* by weighted values.
* 
* @param ticketBlock: matrix with limits and weights for the drawing. All its
* vectors should have lenght two. The weights, instead of percentages, should be
* measured as integers, according to how rare each one should be draw, the rarest
* receiving the smallest value.
* @return The value drawn.
*/
public static int weightedRandomInt(int[][] ticketBlock) throws RuntimeException {
    boolean theVectorsHaventAllLengthTwo = !(haveAllVectorsEqualLength(ticketBlock, 2));
    if (theVectorsHaventAllLengthTwo)
        {throw new RuntimeException("The given matrix has, at least, one vector with length lower or higher than two.");}
    // Need to test for duplicates or null values in ticketBlock!
    
    // Raffle urn building:
    int raffleUrnSize = 0, urnIndex = 0, blockIndex = 0, repetitionCount = 0;
    for(int[] ticket: ticketBlock){raffleUrnSize += ticket[1];}
    int[] raffleUrn = new int[raffleUrnSize];
    
    // Raffle urn filling:
    while (urnIndex < raffleUrn.length){
        do {
            raffleUrn[urnIndex] = ticketBlock[blockIndex][0];
            urnIndex++; repetitionCount++;
        } while (repetitionCount < ticketBlock[blockIndex][1]);
        repetitionCount = 0; blockIndex++;
    }
    
    return raffleUrn[randomInt(0, raffleUrn.length)];
}

Random weighted selection in Java

8 Answers