Joe Lemmer

Ranch Hand

Posts: 171

posted 8 years ago

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

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

OCPJP 85%

Jeff Storey

Ranch Hand

Posts: 230

posted 8 years ago

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:

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

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:

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

Ranch Hand

Posts: 171

posted 8 years ago

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

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

OCPJP 85%

Jeff Storey

Ranch Hand

Posts: 230

posted 8 years ago

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:

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

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:

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

Ranch Hand

Posts: 171

posted 8 years ago

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 :-)

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 :-)

OCPJP 85%

posted 8 years ago

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

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |