Randomly choosing from a list with weighted probabilities

by

The idea:

  • Iterate through all the elements and set the value of each element as the cumulative frequency thus far.
  • Generate a random number between 1 and the sum of all frequencies
  • Do a binary search on the values for this number (finding the first value greater than or equal to the number).

Example:

Element    A B C D
Frequency  1 4 3 2
Cumulative 1 5 8 10

Generate a random number in the range 1-10 (1+4+3+2 = 10, the same as the last value in the cumulative list), do a binary search, which will return values as follows:

Number   Element returned
1        A
2        B
3        B
4        B
5        B
6        C
7        C
8        C
9        D
10       D

More Related Contents:

  1. Unique (non-repeating) random numbers in O(1)?
  2. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  3. What distribution do you get from this broken random shuffle?
  4. Data structures for loaded dice?
  5. Pseudorandom Number Generator – Exponential Distribution
  6. True random number generator [closed]
  7. Generating shuffled range using a PRNG rather than shuffling
  8. Custom Weighted Scale [closed]
  9. Expand a random range from 1–5 to 1–7
  10. How to convert floats to human-readable fractions?
  11. Select k random elements from a list whose elements have weights
  12. Why is quicksort better than mergesort?
  13. Natural Sorting algorithm
  14. What is the fastest integer factorization algorithm?
  15. How to round floats to integers while preserving their sum?
  16. Modulus power of big numbers
  17. Is there an algorithm for color mixing that works like mixing real colors?
  18. How to find two most distant points?
  19. Efficiently reverse the order of the words (not characters) in an array of characters
  20. Create a random permutation of 1..N in constant space
  21. Compute rank of a combination?
  22. Efficiently selecting a set of random elements from a linked list
  23. Skip List vs. Binary Search Tree
  24. reconstructing a tree from its preorder and postorder lists
  25. An algorithm to space out overlapping rectangles?
  26. How does this work? Weird Towers of Hanoi Solution
  27. How do I determine whether my calculation of pi is accurate?
  28. Path generation for non-intersecting disc movement on a plane
  29. A Good and SIMPLE Measure of Randomness
  30. Memory efficient power set algorithm

Leave a Comment