Suppose you have a function (or a magic ball) that is capable of producing a totally random integer between 1 and 5 (inclusive).

Using this, how would you generate a random number (also an integer) between 1 and 7 (inclusive)? (Note that the for the number to be random, all integers between 1 and 7 must have an equal chance of being generated)

Assume that using your 1-5 generator is pretty time-consuming, so you want to minimize the number of times you are going to use it.

Generate two random numbers between a and b between 1 and 5. There are 25 possible combinations. Divide those combinations into groups of 3. There are seven groups, plus four left over. If the generated combination falls into one of these groups, return a number corresponding to that group. Otherwise, try again. C++ code would look something like:


while (true)
{
    int a = rand5();
    int b = rand5();
    int c = (a - 1) * 5 + b - 1;
    int result = (c % 3) + 1;

    if (result <= 7)
        return result;
}
There is no theoretical guarantee that this code will ever return. In fact, I'm not even sure that there is a solution that meets the stated criteria that is guaranteed to return. As a practical matter, though, there is only a 16% chance that it will take more than one iteration, a 2.56% chance that it will take more than two, and a 0.0000011% chance that it will take more than 10. The expected number of calls to rand5() that would be necessary can be found by:

E = 2 + 0.16 * E
E = 2 / (1.0 - 0.16) = ~2.38

Posted by friedlinguini on 2003-06-30 06:56:18