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++/Java:

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%

Java

Download   Run Code

Output (will vary):

1 ~ 29.956%
2 ~ 10.0081%
3 ~ 20.006%
4 ~ 15.0369%
5 ~ 24.993%

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
marshall
Guest

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

Rahul Padhy
Guest

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

roshan
Guest

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.