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).
1 2 3 4 5 6 7 8 9 | 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; } } } |
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | // 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; } |
// 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | 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; } |
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) —
loading...
Last Post: ScriptUnit - VBScript/JScript Unit Tests Runner
Next Post: How to Allow Images Instead of URL in WordPress Comments?
I guess the solution #1 is wrong. There has to be int i = 5 * (rand5() – 1) + (rand5() – 1); Otherwise i is just one of 0, 6, 12 or 18.
yes, you are right, corrected. thanks