Pick items from list with probability based upon property of list member ?

[duncan smith]

southof40 wrote:
> I have list of of N Vehicle objects - the only possible vehicles are
> cars, bikes, trucks.
> 
> I want to select an object from the list with a probability of : cars
> 0.7, bikes 0.3, trucks 0.1.
> 
> I've currently implemented this by creating another list in which each
> car object from the original list appears 7 times, each bike 3 times
> and each truck once. I then pick at random from that list.
> 
> This works but seems very clunky to me. Can anyone suggest a better
> data structure which would support the 'weighted randomness' I'm
> after ?
> 
> I'm not fixed on the idea of using a list - could be a dictionary,
> tree whatever .
> 
> Thanks in advance.
> 

Try googling for "alias table".  Efficient if you're selecting many 
random objects from the same mass function.  Better than binary search 
on the cumulative mass function in big-O terms (but maybe not in 
practical terms for reasonable sized problems).  Neither approach is as 
efficient as the one you outlined, but the required list size might be 
an issue for some sets of probabilities.

Duncan