Problem

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. (i.e., implement rand7() using rand5()).

OR

Using a function rand5() that returns an integer from 1 to 5 (inclusive) with uniform probability, implement a function rand7() that returns an integer from 1 to 7 (inclusive).

Solution

This appear to be one of those probabilistic analysis questions. You should be familiar with the concept of expected value, as it could be extremely helpful in probabilistic analysis.

This solution is based upon Rejection Sampling. The main idea is when you generate a number in the desired range, output that number immediately. If the number is out of the desired range, reject it and re-sample again. As each number in the desired range has the same probability of being chosen, a uniform distribution is produced.

Method 1 - Without using extra space

To solve this problem, we need to generate a number between 1 and 7 using a function rand5() that returns integers uniformly between 1 and 5. The essential strategy is to construct a wider range of values using rand5() and then map those values to our desired range (1 to 7).

Here’s a step-by-step approach:

  1. Generate a wider range: Use rand5() in pairs to generate numbers between 1 and 25 (since ( 5 * 5 = 25 )).
  2. Select a subset: Map those values to a range between 1 and 7 while ignoring values outside a multiple of 7 (i.e., 1 to 21 are acceptable as ( 21 = 7 * 3 )).
  3. Retry if necessary: If the generated number is outside 1 to 21, repeat the process until a valid number is obtained.

Code

Java
public class Rand7FromRand5 {

	static Random rand = new Random();

	// Mock implementation of rand5()
	public static int rand5() {
		return rand.nextInt(5) + 1;
	}

	public static int rand7() {
		while (true) {
			// Generate a number in range 0 to 24
			int num = (rand5() - 1) * 5 + (rand5() - 1);
			// Accept numbers in 1 to 21 and map to 1 to 7
			if (num < 21) {
				return (num % 7) + 1;
			}
		}
	}
}
Python
import random


# Mock function for rand5
def rand5():
    return random.randint(1, 5)


def rand7():
    while True:
        # Generate a number in range 0 to 24
        num = (rand5() - 1) * 5 + (rand5() - 1)
        # Map the numbers in range 1 to 21 to 1 to 7
        if num < 21:
            return (num % 7) + 1

Method 2 - Using 2D Array

I like this solution as mentioned here. Obviously, we have to run rand5() function at least twice, as there are not enough numbers in the range of 1 to 7. By running rand5() twice, we can get integers from 1 to 25 uniformly. Why?

Code

Java
public class Rand7FromRand5 {

	static Random rand = new Random();

	public int rand5() {
		return rand.nextInt(5) + 1;
	}

	private int vals[5][5] = {
		{ 1, 2, 3, 4, 5 },
		{ 6, 7, 1, 2, 3 },
		{ 4, 5, 6, 7, 1 },
		{ 2, 3, 4, 5, 6 },
		{ 7, 0, 0, 0, 0 }
	};

	public int rand7() {
		int ans = 0;
		while (ans == 0) {
			int i = rand5();
			int j = rand5();
			ans = vals[i-1][j-1];
		}
		return ans;
	}
}

In the above array, if we generate index upto 21 elements i.e. rows 0 to 3 and columns 0 to 5 and for row 4 only column 1.  To put it differently we can also do following:

public class Rand7FromRand5 {

	static Random rand = new Random();

	public int rand5() {
		return rand.nextInt(5) + 1;
	}

	public int rand7() {
		int ans = 24;
		while (ans > 21) {
			int i = rand5();
			int j = rand5();
			ans = j + (i-1)*5;
		}
		return ans % 7 + 1;
	}
}

Since 25 is not a multiple of sevens, we have to use rejection sampling. Our desired range is integers from 1 to 21, which we can return the answer immediately. If not (the integer falls between 22 to 25), we reject it and repeat the whole process again.

Now let’s get our hands dirty to calculate the expected value for the number of calls to rand5() function.

E(# calls to rand5) = 2 * (21/25) +
3 * (4/25) * (14/20) +
4 * (4/25)2 * (6/20) +
...

∞
= ∑ 2k * (9/49)k-1 * (40/49)
k=1

= (80/49) / (1 - 9/49)2
= 2.21

How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it’s a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That’s what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don’t get a good result, we keep throwing darts.

In worst case, it may run infinitely. 

Also, read this good answer on stackoverflow. 

Also note, that we can use another way. 5rand5()*rand5() + rand5() can also be used. If X and Y are independent and uniformly distributed on the set Srand5()_5 = {0, 1, 2, 3, 4}, then

  1. 5rand5()*X + Y is uniformly distributed on the set {0,...,24}, but
  2. 3*X + Y is not uniformly distributed on {0,...,16} and neither is its restriction on {0,...,13}

is not uniformly distributed. For example, it generates 0 in only one way, but 3 two ways, so 3 is more likely to occur than 0. It’s just like 2 * rand5() * rand5(), 4 * rand5() + rand5(), etc. But 5 * rand5() + rand5() is uniformly distributed. It is like generating two random digits of a base-5 number.

00 => 0
01 => 1
02 => 2
03 => 3
04 => 4
10 => 5
11 => 6
12 => 7
...

There is only and only one way to generate each number from 0 to 24.