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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
			}
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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;
	}
}
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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;
	}
}
1
2


Now let’s get our hands dirty to calculate the [expected value](http://en.wikipedia.org/wiki/Expected_value) for the number of calls to rand5() function.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


In worst case, it may run infinitely. 

Also, read [this](http://stackoverflow.com/a/891304/3222727) good answer on stackoverflow. 

Also note, that we can use another way. `5`rand5()`*rand5() + rand5()` can also be used. If X and Y are [independent](http://en.wikipedia.org/wiki/Independence_%28probability_theory%29) and [uniformly distributed](http://en.wikipedia.org/wiki/Uniform_distribution_%28discrete%29) on the set `S`rand5()`_5 = {0, 1, 2, 3, 4}`, then

1. `5`rand5()`*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.
1
2
3
4
5
6
7
8
9

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