0

I am creating a set of items and with each I am counting its number of occurrences in a sample. Later I wish to choose an item at random but I want the chance of choosing any particular item to be equal to the number of occurrences as compared to the total of all occurrences of all items.

I believe I have found a nice solution but I'm interested what the standard term for this concept is and what the standard methods of achieving it are.

hippietrail
  • 15,848
  • 18
  • 99
  • 158
  • 2
    Lots of duplicates: The earliest I know of is [How do I generate points that match a histogram? ](http://stackoverflow.com/questions/423006/), but the related column on you question has some more like [C: picking a random item based on probabilities](http://stackoverflow.com/questions/2772882/) and [Generate Random Numbers with Probabilistic Distribution](http://stackoverflow.com/questions/3109670/) [Adjust items chance to be selected from a list](http://stackoverflow.com/questions/1589321/) [how to implement non uniform probability distribution?](http://stackoverflow.com/questions/3094873/) – dmckee --- ex-moderator kitten Dec 07 '10 at 06:50

1 Answers1

1

This doesn't have a name on it's own, but it's an important step in updating your beliefs based on evidence during PARTICLE FILTERING which is probably the term you're looking for.

Choose a random number (r) from 0 to n-1 (n is the total number of occurrences of all items). Then iterate over each item and subtract the number of occurrences from r. When you get below zero, select the last item. Note that it's not important to group the same item in the same place. You may have repeats and this will still work.

Alternatively, if your occurrences are stored individually in an array (rather than a histogram), simply select a random index from the array.

dspyz
  • 5,280
  • 2
  • 25
  • 63