CODEWITHSUNDEEP
javaarraylistrandom
Jermano
Jermano

Reputation: 89

Choose an object randomly with different probability

I have the following problem:

I need to choose a random object from an List. This is simple, if all elements would have the same chance to be picked.

In my case, the chance of an object being picked is stored in another List. So I need a method, that randomly picks an element from the list based on the other List.

EDIT: E.g.

List<String> objects = Arrays.asList("one","two","three");
List<Double> chance = Arrays.asList(0.25, 0.25, 0.5);

Now I want the String "one" and "two" with a chance of one out of four and the String "three" with a chance of one out of two.

Thank you for any advice.

Upvotes: 0

Views: 2088

Answers (1)

Nicolas Filotto
Nicolas Filotto

Reputation: 45005

You could a TreeMap with as key the current total of the previous probabilities and as value the corresponding object, then generate a random number between 0 and 1, and finally use ceilingEntry(K key) to get the object corresponding to the first key that is greater or equal to the current random value.

Something like:

List<String> objects = Arrays.asList("one","two","three");
List<Double> chance = Arrays.asList(0.25, 0.25, 0.5);

// Build the tree map
TreeMap<Double, String>  map = new TreeMap<>();
double total = 0.0d;
for (int i = 0; i < objects.size(); i++) {
    map.put(total += chance.get(i), objects.get(i));
}
System.out.printf("The generated is map %s%n", map);

// The generator of random numbers
Random generator = new Random();
// Generate a random value between 0 and 1
double value = generator.nextDouble();
// Get the object that matches with the generated number
String object = map.ceilingEntry(value).getValue();
System.out.printf("The current value is %f corresponding to '%s'%n", value, object);

Output:

The generated map is {0.25=one, 0.5=two, 1.0=three}
The current value is 0,048460 corresponding to 'one'

So here:

  1. If the random value is lower or equal to 0.25, we will get "one".
  2. If the random value is between 0.25 (excluded) and 0.50 (included), we will get "two".
  3. If the random value is between 0.50 (excluded) and 1.0 (included), we will get "three".

Thanks to the fact that nextDouble() returns a double value uniformly distributed between 0.0 and 1.0, this is good enough to get the expected distribution.

Upvotes: 3

Related Questions