CODEWITHSUNDEEP
javaalgorithmrandom
Josh
Josh

Reputation: 675

How to choose a random number in a weighted way

For example if I have an array of ints like this:

int[] list = {1, 4, 2};

And I want to choose one of these 3 numbers, but have the greater values get chosen more frequently:

1 get chosen 1/7 of the time
4 gets chosen 4/7 of the time
2 gets chosen 2/7 of the time

How can I write a function for this, if there isn't already one in Java.

Edit: I'm looking for an efficient solution, O(n) or better.

I'm going to be running this code a lot times in many threads. Building a new list is not sufficient.

Upvotes: 2

Views: 881

Answers (3)

icza
icza

Reputation: 417642

You can simply use Math.random() to get a random number in the range of 0..1, and choose the number at the index whose cumulative weights "cover" the random number:

public static int random(int[] numbers, double[] weights) {
    double r = Math.random();
    
    double sum = 0;
    for (int i = 0; i < weights.length; i++) {
        sum += weights[i];
        if (r < sum)
            return numbers[i];
    }
    
    return 0; // You can only get here if sum weights is less than 1
}

This solution chooses you a random number according to the weights you provide in O(N). In most cases the algorithm doesn't even read the whole weights array. This is as good as it can get. Maximum steps is N, average number of steps is N/2.

Notes:

  • On average the method will be faster if bigger weights are at the beginning of the weights array.

  • The sum of the weights is expected to be 1. If the sum of the weights is less than 1, this method might return 0 (with a probability of 1-sum(weights)).

Upvotes: 1

rishiAgar
rishiAgar

Reputation: 168

1) Take the sum(S) of elements(A[i]) 2) Get Cumulative sum list(C[i]) 3) Get Random Value(R) from 0 to S-1 4) If R < C[i], your random value is A[i]

Cumulative Sum Range    Index in the Cumulative Array      Value in Original Array  
-----------------      -----------------------------      ----------------------
 0 <= x < 1                      0                            1
 1 <= x < 6                      1                            4
 6 <= x < 7                      2                            2

Upvotes: 0

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

Accumulate the values in list and call the resulting sum S. Now generate a random number from 0 to S - 1. Iterate once more over list and for each element do the following: if the element is greater then S than choose that element. Otherwise decrease S by the element's value and continue on to the next element.

Upvotes: 3

Related Questions