Most efficient algorithm to print 1-100 using a given random number generator

Problem Detail: 

We are given a random number generator RandNum50 which generates a random integer uniformly in the range 1–50. We may use only this random number generator to generate and print all integers from 1 to 100 in a random order. Every number must come exactly once, and the probability of any number occurring at any place must be equal.

What is the most efficient algorithm for this?

Asked By : Raj Wadhwa

Answered By : Vor

I thought (so it can be wrong :-) of this $O(N^2)$ solution that uses the Fisher-Yates shuffle. In order to keep uniform distribution with good approximation (see EDIT section below) at every iteration you can use this trick to produce a value krand between $0$ and $k-1$:

 // return a random number in [0..k-1] with uniform distribution  // using a uniform random generator in [1..50]  funtion krand(k) {        sum = 0    for i = 1 to k do sum = sum + RandNum50() - 1    krand = sum mod k  } 

The Fisher-Yates algorithm becomes:

arr : array[0..99] for i = 0  to 99 do arr[i] = i+1; // store 1..100 in the array for i = 99 downto 1 {   r = krand(i+1)  // random value in [0..i]   exchange the values of arr[i] and arr[r] } for i = 0 to 99 do print arr[i] 

EDIT:

As pointed out by Erick the krand function above doesn't return a truly uniform distribution. There are other methods that can be used to get a better (arbitrarily better) and faster approximation; but (up to my knowledge) the only way to get a truly uniform distribution is to use the rejection sampling: pick $m = \lceil \log_2(k) \rceil$ random bits and if the number $r$ obtained is less than $k$ return it, otherwise generate another random number; a possible implementation:

function trulyrand(k) {     if (k <= 1) return 0     while (true) { // ... if you're really unlucky ...       m = ceil(log_2 (k) ) // calculate m such that k < 2^m       r = 0  // will hold the random value       while (m >= 0) {  // ... will add m bits                 if ( rand50() > 25 ) then b = 1 else b = 0   // random bit         r = r * 2 + b  // shift and add the random bit         m = m - 1       }             if (r < k) then return r  // we have 0<=r<2^m ; accept it, if r < k     } } 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2576