Generate Random Input from an Array according to given Probabilities

Write an algorithm to generate any one of the given N numbers according to given probabilities.


 

For example, consider the below array of integers and their probabilities:

      input[] = { 1, 2, 3, 4, 5 };
probability[] = { 30, 10, 20, 15, 25 }; // total probability should sum to 100%

The solution should return 1 with 30% probability, 2 with 10% probability, 3 with 20% probability, and so on for every element in the array.

 


 

Algorithm:
  1. Construct an sum array S[] from the given probability array P[] where S[i] holds the sum of all P[j] for 0 <= j <= i.
     
  2. Generate a random integer from 1 to 100 and check where it lies in S[].
     
  3. Based on the comparison result, return the corresponding element from the input array.

 

Below is its implementation in C/C++:

C


 

Download   Run Code

Output (will vary):

1 ~ 29.96%
2 ~ 10.05%
3 ~ 20.04%
4 ~ 14.91%
5 ~ 25.04%

C++


 

Download   Run Code

Output (will vary):

1 ~ 30.017%
2 ~ 10.0539%
3 ~ 20.0162%
4 ~ 14.9635%
5 ~ 24.9494%

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
marshall
Guest
marshall

Since the prob_sum vector is sorted, you can use binary_search or lower_bound instead of scanning linearly.

Rahul Padhy
Guest
Rahul Padhy

Could you please give a bit more of an explanation for the algorithm ?

roshan
Guest
roshan

I do not understand why this algorithm will be correct? It may possible generated r is always less than the first item in probability vector.

wpDiscuz