Choose an object randomly with different probability

Question

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.

your question is not clear at all, can you share some code or and input output result ? — Youcef LAIDANI
– Youcef LAIDANI, Commented Jan 31, 2017 at 18:51
same chance mean that if child already pick then no more pick for the chosen some interval? — Iqbal Rizky
– Iqbal Rizky, Commented Jan 31, 2017 at 18:56
I presume your probabilities sum to 1? Then just use Math.random() to pick a number [0 .. 1) and then walk the probably List and sum until you find the first element that exceeds your sum. Return the item at that index. — Boris the Spider
– Boris the Spider, Commented Jan 31, 2017 at 18:58
@Boris's suggestion is good. Or, if you're going to do this a lot and performance matters, you can form a list that's the cumulative sum of the probabilities and then do binary search to find the index where the total probability first exceeds the random number you've drawn. That will be quite a bit faster if you have to draw lots of samples. — Oliver Dain
– Oliver Dain, Commented Jan 31, 2017 at 19:06

Nicolas Filotto · Accepted Answer · 2017-02-01 19:03:11Z

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:

If the random value is lower or equal to 0.25, we will get "one".
If the random value is between 0.25 (excluded) and 0.50 (included), we will get "two".
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.

Collectives™ on Stack Overflow

Choose an object randomly with different probability

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related