On Jan 30, 8:57 pm, "Jialin" <[EMAIL PROTECTED]> wrote:
> Question:
>
> Given a program which can generate one of {1, 2, 3, 4, 5} randomly.
> How can we get another generator which can generate one of
> {1,2,3,4,5,6,7} randomly?
>
> Thank you!
If you generate random 1 to 5 twice, there are 25 equally likely
outcomes. Discard 4 of these whenever they occur. Then you have 21
equally likely outcomes. Split these into 7 equally likely ranges.
int rand7()
{
for (;;) {
int n = 5 * (rand5() - 1) + (rand5() - 1); // n lies in 0..24
if (n < 21) return n / 3 + 1;
}
}
The probabily you'll loop is 4/25 each time around. You can decrease
this as far as you like, but never to zero because 5 and 7 are
mutually prime. For example if you generate 5 numbers (rather than 2)
in 1 to 5, there are 5^5 = 3125 outcomes. Discard 3 of these and
split the remaining 3122 = 447 * 7:
int rand7()
{
for (;;) {
int n = 5 * (5 * (5 * (5 * (rand5() - 1) + (rand5() - 1)) +
(rand5() - 1)) + (rand5() - 1)) + (rand5() - 1);
if (n < 3122) return n / 446 + 1;
}
}
Here a loop will occur with probability of less than 0.1%. Maybe
there is a clever way to eliminate discards completely, but I can't
see it.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
