Generating m distinct random numbers in the range [0..n-1]

by

Pure mathematics:
Let’s calculate the quantity of rand() function calls in both cases and compare the results:

Case 1:
let’s see the mathematical expectation of calls on step i = k, when you already have k numbers chosen. The probability to get a number with one rand() call is equal to p = (n-k)/n. We need to know the mathematical expectation of such calls quantity which leads to obtaining a number we don’t have yet.

The probability to get it using 1 call is p. Using 2 calls – q * p, where q = 1 - p. In general case, the probability to get it exactly after n calls is (q^(n-1))*p. Thus, the mathematical expectation is
Sum[ n * q^(n-1) * p ], n = 1 --> INF. This sum is equal to 1/p (proved by wolfram alpha).

So, on the step i = k you will perform 1/p = n/(n-k) calls of the rand() function.

Now let’s sum it overall:

Sum[ n/(n - k) ], k = 0 --> m - 1 = n * T – the number of rand calls in method 1.
Here T = Sum[ 1/(n - k) ], k = 0 --> m - 1

Case 2:

Here rand() is called inside random_shuffle n - 1 times (in most implementations).

Now, to choose the method, we have to compare these two values: n * T ? n - 1.
So, to choose the appropriate method, calculate T as described above. If T < (n - 1)/n it’s better to use the first method. Use the second method otherwise.

More Related Contents:

  1. Random generation of numbers? [closed]
  2. Create Random Number Sequence with No Repeats
  3. What is the efficient way to count set bits at a position or lower?
  4. Need for predictable random generator
  5. What is a good random number generator for a game?
  6. Is it possible to map string to int faster than using hashmap?
  7. Fastest way to get the integer part of sqrt(n)?
  8. Generate N random numbers within a range with a constant sum
  9. Where is likely the performance bug here? [closed]
  10. How to find out how many bits are set (equal 1) in the product of two integers [closed]
  11. Best way to reverse a string
  12. Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
  13. How to “return an object” in C++?
  14. Rotating a point about another point (2D)
  15. Fast textfile reading in c++
  16. Which is faster: Stack allocation or Heap allocation
  17. C++ : Catch a divide by zero error
  18. Generate random numbers following a normal distribution in C/C++
  19. Fast ceiling of an integer division in C / C++
  20. How much is the overhead of smart pointers compared to normal pointers in C++?
  21. How to do unsigned saturating addition in C?
  22. Why does this delay-loop start to run faster after several iterations with no sleep?
  23. How do I generate thread-safe uniform random numbers?
  24. Efficiency of the STL priority_queue
  25. What’s the fastest way to pack 32 0/1 values into the bits of a single 32-bit variable?
  26. Writing function definition in header files in C++
  27. Algorithm to add or subtract days from a date?
  28. Creating N nested for-loops
  29. C++11 random numbers
  30. How to find Longest Common Substring using C++

Leave a Comment