Select according to probability

[airerdem]

Hi,

I have a vector and there are probability values of each element.

I want to select 10 of them according to these probabilities.

To visualize;

Array[0].probability=0.56
Array[1].probability=0.43
Array[2].probability=0.08
Array[3].probability=0.96
Array[4].probability=0.23
Array[5].probability=0.11
.
.
.
Array[99].probability=0.76

And I want to select only 10, according to these probabilities of selecting.

Thanks in advance

[onur]

I'd do it like this:

* Add a field "accumulatedProbability"

Array[0].accumulatedProbability = Array[0].probability;
for (int i = 1; i < 100; ++i)
   Array[i].accumulatedProbability = Array[i-1].accumulatedProbability + Array[i].probability;

Array[99].accumulatedProbability should then be 1.0.

* next generate a random number between 0 and 1. (or 0..Array[99].accumulatedProbability)
* find the smallest index (by using binary search) whose accumulatedProbability is larger than the random number.

If you are interested in the math behind the scene:
http://en.wikipedia.org/wiki/Cumulative_distribution_function

[airerdem]

Thank you ;)