Selecting from a range

[Joe Lemmer]

Hi there,

I've got a bit of a tricky question here.

I want to make a random selection from, say, 5 different choices. If I wanted to have an equal chance of choosing each one, then I could just create a random number between 0 and 1, multiply this by 5, and this would select my choice. No prob.

What I would like to do, however, is make a choice when there are different probabilities for each choice. Lets say, 5% for choice 1, 20% for choice 2, 30% for choice 3 etc.

If I had the percentages for each choice then I might say that given a random number between 1 and 100, then choice 1 would get chosen if the number were between 1 and 5, choice 2 would get chosen if the number were between 6 and 20, choice 3 would get chosen if the number were between 21 and 50 etc.

So far so good, but what I can't get my head around is how I would code the fact that choice 2 is '5 to 20' !!

I thought of having an array with the total number for the possiblities (this might be more than 100, for instance if I had a choice that had a probability of 30, but there were 4 other choices with a probability of 50, then the total would be out of 230). So in this case the array would be 230 units long. Then I would fill 0 to 29 with a string representing the first choice and so on. When I get my random number between 0 and 229 then I check the array to find the id string with the name of my choice. I realise that this is a pretty rubbish solution, especially as my program will need to make lots of these probability decisions and I don't know how heavy dutymaking an array is that is that long.

Another solution would be to use if statements and say 'if the random number is between 0 and 29 then go to choice 1' etc. The problem with this is the solution needs to be able to handle different numbers of choices with varying probabilities.

Any ideas would be very much appreciated.

Cheers guys

Joe

[Jeff Storey]

Joe,

I think you're on the right track here (there may be more optimal solutions, but let's work with what you have).

I've assumed that you'll be working in units no smaller than 1% (so integers will work, but you can adapt for finer granularity if needed). So, we'll always choose from a pool of 100 numbers. Given this example:
Choice 1 - 10% (1-10)
Choice 2 - 90% (11-100)

You could have a Range object that looks something like:

class Range {
   private final int startVal;
   private final int endVal;
  
   public Range(int startVal, int endVal) {
     this.startVal = startVal;
     this.endVal = endVal;
   }

   public boolean isNumberInThisRange(int number) {
      return number >= startVal && number <= endVal;
   }

}

Now you could store a Map of choice/range pairs. Then pick a random number between 1-100 and for each of the choices, check if that number is within the corresponding range.

An alternative solution if you need to do faster calculations would be to have an ordered list, and say choice 1 starts at 1, choice 2 starts at 11, etc. Then you could use some of the Collections methods to determine where a number would fit in this list and you could figure out which choice it's in.

Hope this helps,
Jeff

[Joe Lemmer]

Jeff,

Thanks very much for your helpful reply and code.

The key to the first method would be getting the start and end values that are used as parameters to your constructor. I'm sure I could come up with something.

Also I'm very interested in your ordered list idea. I'm not exactly sure what an ordered list is though. Is that the List class in the API? So, if I used an ordered list, then I put the choice in at the same index as the startVal. Then when I get a random number, I search through the lists index and get it to search downward to find the first non-null index. Is that what you had in mind?

It's really intrigued me, actually, this problem. I want to be able to have actions in my program alter the probability of future choices as a primitive sort of 'learning' response. Each time a user makes a specific action, then the probability of a certain action is altered in some predefined way. I'm sure a lot of people use this sort of thing. Maybe in games or something?

Thanks again.

Regards

Joe

[Jeff Storey]

Joe,

Glad I could help. I'll elaborate a little more, but first I want to address something in your first post that I glossed over a little too quickly. You gave an example of a case where you might have an array with 230 elements because choice 1 has a probability of 30% and choices 2-5 have a probability of 50%. By definition, the sum of the probabilities must be 100%, so I would think all of your probabilities would need to add up to 100%.

For the ordered list, all I meant was any java list (i.e. ArrayList or LinkedList) where you put the elements in order, such as 1, 2, 3...100. So, let's go through a concrete example (I'll use my assumption above that the probabilities will add up to 100%):

Choice 1 - 20%
Choice 2 - 30%
Choice 3 - 50%

You could create a list with 2 (generally, n-1 where n is the number of choices) elements: 20, 50 since 1-20 will be choice 1, 21-50 will be choice 2 and choice will be the remaining 51-100. Then select a random number, and let's say it comes out to 25. Find which index in the list corresponds to the number 25, here is some pseudocode:

// The randomly picked number
int randNum = 25;
int choice = -1;
// Note you'll want to use an ArrayList
// here since we'll be accessing by the
// list index and it is much faster than a linked list
for ( int i = 0; i < list.size(); i++ ) {
  if ( randNum <= list.get(i) ) {
       // The +1 is because the choices are
       // labeled 1-3, not 0-2, but if the choices
      // are stored in a list, the first will be
      // index 0, so you wouldn't need the +1
      choice = i+1;
      break;
  }
}

// Another note: since the list will be populated in
// ascending order, you could also use the
// Collections.binarySearch method to find a similar result.
// With a small list, I doubt it really makes much of a
// noticeable difference, but if you're interested,
// you can always do some performance testing
// to check (but I don't think we're there yet).

In this case, randNum would be less than list.get(1) (25 <= 50), so the choice number would be 2. You'll have to be careful with the equals sign (when to use <= vs just <) and when to use 0 based index and 1 based to be sure you're getting the exact values you want, but I'll leave those details up to you.

Also, when you want your program to learn and change the ranges, all it would need to do is change the values in the list.

Jeff

[Joe Lemmer]

Jeff, this is an extremely cunning plan and a lot more lightweight (if that's the right expression) than I'd hoped for.

Thank you!

I was thinking that I'd have to use the actual index to hold the value, so I would have had a string at index 20 and another one at index 50 etc and a lot of wasted space in between.

I'm looking forward to putting this into action (although the speed of my implementation will no doubt
end up being measured in geological time).

Cheers again

Joe :-)

[Rob Spoor]

One more advice: use Random.nextInt(int n) instead to create a random number between 0 and n (exclusive).

[Joe Lemmer]

Thanks Rob