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

[duncan smith]

duncan smith wrote:
> 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

BTW, the alias table approach is basically a means of getting round the 
problem of needing large lists.  Assuming your probabilities should be 
0.7, 0.2 and 0.1 you could construct a list of 3 objects.  The first 
would be 100% car, the second would be 60% bike and 40% car, the third 
would be 30% truck and 70% car.  Choose an object at random, then the 
vehicle type according to the mass function associated with the object. 
  The alias table approach only requires the generation of a single 
uniform random variate and a single comparison (once you've constructed it).

Duncan