Interview Question: Construct Evenly-Distribution Rand7 based on Rand5

The Interview Question: Assume the Rand5() gives a random integer from 1 to 5. Each possible return is given with the same probability. How do you construct the Rand7() function that returns the evenly-distribution results of integer 1 to 7?

[0-24]

rand5() – 1 gives the range 0 to 4 inclusive. First we construct the range [0, 24]. We only use the range [0, 21] to construct 1 to 7 (mod 7 and plus 1).

int rand7() {
	for(;;) {
		// [0, 24]
		int i = 5 * (rand5() - 1) + (rand5() - 1);
		if( i < 21 ) { // the first 21 numbers (0 to 20) are evenly distributed.
			return i % 7 + 1;
		}
	}
}

[0-1]

Similarly, we can construct the evenly-distributed range 0 to 1, then construct 0 to 7, then skip 0 to get the result of 1 to 7.

// Gen 0, 1 equal probability
int rand01() {
    int i = rand5();
    while (i > 4) {i = rand5();}
    return i % 2;
}
 
// Gen 0, 1, 2, 3, 4, 5, 6, 7 equal probability
int rand07() {
    return rand01() * 4 + rand01() * 2 + rand01();
}
 
// Gen 1, 2, 3, 4, 5, 6, 7 equal probability
int rand7() {
    int i = rand07();
    while (i == 0) {i = rand07();}
    return i;
}

Matrix

We create a matrix 5 rows and 5 columns, and we initialize the matrix with all zeros. We only fill the matrix with equal numbers of 1 to 7 (3 times each number). We skip the zeros and return a random integer otherwise.

int matrix[5][5];
memset(matrix, 0, sizeof(matrix));
 
// Set matrix with num 1-7, each number has the same count.
for (int i = 1; i <= 7; ++i) {
    for (int j = 0; j < 3; ++j) {
        *matrix++ = i;
    }
}
 
int rand7() {
    int i; 
    do { 
        i = matrix[rand5() - 1][rand5() - 1];
    } while (i == 0); 
    return i;
}

–EOF (The Ultimate Computing & Technology Blog) —