0

I have a list of values, keyed with doubles between 0 and 1 that represent how likely I think it is for a thing to be useful to me. For example, for getting an answer to a question:

0.5   call your mom
0.25  go to the library
0.6   StackOverflow
0.9   just Google it

So, we think that Googling it is (about) twice as likely to be helpful as asking your mom. When I attempt to figure out the next thing to do, I'd like "just Google it" to be returned about twice as often as "call your mom".

I've been searching for solutions with little success. Most of the things that I've found rely on having integer keys (like How to randomly select a key based on its Integer value in a Map with respect to the other values in O(n) time?), which I don't have and which I can't easily generate.

I feel like there should be some Java datatype that can do this for me. Any suggestions?

Community
  • 1
  • 1
Karen
  • 885
  • 2
  • 7
  • 11
  • The answer you link to _is_ applicable when you have `double` values; it's not integer-specific. – Louis Wasserman Jul 19 '12 at 14:58
  • I don't think that this is the case. Consider the line `int index = this.rand.nextInt(this.sum) + 1;`. The `Random` package does not have an equivalent function to generate `doubles` in between 0 and a given maximum. In addition, adding 1 to the sum is obviously not correct - but it isn't evident what constant I would add to the sum instead to ensure that the maximum-weight element can be selected. – Karen Jul 19 '12 at 15:04
  • Multiply `rand.nextDouble()` by the sum, and don't add anything. – Louis Wasserman Jul 19 '12 at 15:12

3 Answers3

1

You can think of a solution based on the java interface NavigableMap, and if you use the TreeMap implementation you will always get a O(logn) complexity.

You can use one of the following:

  • lowerEntry
  • ceilingEntry
  • floorEntry
  • higherEntry

Now you just need to extract random numbers with the right probability. For that I would refer to this post:

How to generate a random number from specified discrete distribution?

Community
  • 1
  • 1
Edmondo
  • 19,559
  • 13
  • 62
  • 115
1

If I understood correctly, what you're looking for is a weighted random.
You should sum all your weights, and maybe normalize this to an integer value, so you will be able to use the rand.nextInt as suggested by comments.
Normalization can be done by multiplying by 100 for example, so your normalized weights are now:
50, 25, 60, 90 - The sum is 225.
You should define ranges:
0 - 49 is for "calling your mum"
50 - 74 - is for "go to library"

Now you need to perform this.rand.nextInt(sum) - and get a value,
and this value should be mapped to one of the defined ranges.

Yair Zaslavsky
  • 4,091
  • 4
  • 20
  • 27
0

If you keep track of what the total value of the probabilities are, you can do something like this:

double interval = 100;
double counter = 0;
double totalProbabilities = 2.25;
int randInt = new Random().nextInt((int)interval);
for (Element e: list) {
  counter += (interval * e.probability() / totalProbabilities);
  if (randInt < counter) {
    return e.activity();
  }
}
Keppil
  • 45,603
  • 8
  • 97
  • 119