php - Fixed Proportionate Selection -

php - Fixed Proportionate Selection -

i have set of elements , need take 1 element out of it. each element associated percentage chance. percentages add together 100.

i need take 1 out of element chances of element beingness chosen equal percent value. if element has 25% chance, supposed have 25% chances of getting chosen. in other words, if take elements 1 mil times, element should chosen near 250k times.

what describe multinomial process.

http://en.wikipedia.org/wiki/multinomial_distribution#sampling_from_a_multinomial_distribution

they way generate such random process this: ( i'll utilize pseudo code should easy create in real code. )

sort 'boxes' in reverse order of probability: (not needed. it's optimization) have illustration values=[0.45,0.3,0.15,0.1]

then create 'cumulative' distribution, sum of elements index <=i. pseudocode:

cumulant=[0,0,0,0] // initiate s=0 j=0 size()-1 { s=s+values[i] ; cumulant[i]=s }

in our case cumulant=[0.45,0.70,0.85 ,1 ]

make uniform random number x between 0 , 1. php: http://php.net/manual/en/function.rand.php

the resulting random box index is

the highest cumulant[i]< x

pseudocode:

for j=0 size()-1 { if !(cumulant[i]<){ print "your index ",i break; }

that it. random index going point 3.

if sort suggested above, means final search faster. example, if have vector of probabilities: 0.001 0.001 0.001 0.001 0.996 then, when sort it, have @ index i=0, since random number x lower 0.996. if sort pays off or not depends on if repeatedly utilize same 'boxes'. so, yes 250k tries help lot. remember box index sorted vector.

php algorithm math probability