4

This is an interview question:

Given a function which generates a random number in [1,5],we need to use this function to generate a random number in the range [1,9]. I thought about it a lot but am not able to write an equation where ramdomness is satisfied. People please answer.This might be helpful maybe in some future interviews.

doctore
  • 518
  • 9
  • 18
  • do you want to have uniform probability distribution too ? – S J Jun 19 '13 at 11:49
  • thats what randomness means i guess. – doctore Jun 19 '13 at 11:50
  • Given how the question is asked, I'm fairly sure that it has to yield a uniform distribution. Otherwise it makes no sense to ask that question. – Joey Jun 19 '13 at 11:50
  • Does the generated function generate integers or real numbers? – Koterpillar Jun 19 '13 at 11:54
  • You can have a random number generator that doesn't have a uniform probability distribution. The trivial example is rolling two six sided dice. It's certainly random, but you're much less likely to roll a 12 than you are a 7. – Kevin Jun 19 '13 at 11:56
  • This question has been answered already: http://stackoverflow.com/questions/137783/expand-a-random-range-from-15-to-17 – Lasse V. Karlsen Jun 19 '13 at 12:01
  • @doctore - this is quite famous question. have a look at http://stackoverflow.com/questions/137783/expand-a-random-range-from-15-to-17 – S J Jun 19 '13 at 12:02

3 Answers3

8

Adapted from "Expand a random range from 1–5 to 1–7"

It assumes rand5() is a function that returns a statistically random integer in the range 1 through 5 inclusive.

int rand9()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 8, 9, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 8, 9, 0, 0 },
        { 0, 0, 0, 0, 0 }
    };

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

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 9, 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.

this can run forever in the worst case, but statistically the worst case never happens. :)

Community
  • 1
  • 1
S J
  • 3,210
  • 1
  • 22
  • 32
  • Answer is Adapted from http://stackoverflow.com/questions/137783/expand-a-random-range-from-15-to-17?lq=1. – S J Jun 19 '13 at 12:09
  • Just curious, if we have a function which generates a random number in [1,5], does it mean we can only create another function that generates a random number in the range [1,25] at most? how about [1,26], is it possible? – CSnerd Oct 18 '16 at 12:55
2
int rand9()
{
    int t1,t2,res = 10;
    do {
        t1 = rand5();
        do {
            t2 = rand5();
        }while(t2==5);
        res = t1 + 5* (t2%2);
    }while(res==10);
    return res;
}

now 1 to 9 has the probability of 1/9.

make some explanation:

t1 has probability of 1/5 to be 1 to 5.

t2,too.but when t2==5,discarded.so t2 has probability of 1/4 to be 1 to 4.that' to say, probability of 1/2 to be odd or even,which makes t2%2 has probability of 1/2 to be 0 to 1.

thus, t1 + 5*(t2%2) has probability of 5/10 to be 1 to 5, and 5/10 to be 6 to 10. but 10 is discarded again,so the rest 9 numbers' probability is 1/9.

vvy
  • 1,963
  • 13
  • 17
  • This isn't random either, numbers 2 and 4 occurs twice as many times as the rest, and 9 none at all. – Lasse V. Karlsen Jun 19 '13 at 12:03
  • I've change res = t1*(1+ t2%2) to res = t1+ 5* t2%2, now it works. – vvy Jun 19 '13 at 12:07
  • 1
    No, it doesn't. The code as it stands now produces numbers from 1 to 6 (and not 7-9), and 2-5 occurs twice as often as 1 and 6. I have a [LINQPad](http://linqpad.net) program here you can try that shows you: https://www.dropbox.com/s/p7m9sb4jqto9f15/SO17190340.linq – Lasse V. Karlsen Jun 19 '13 at 12:10
  • @LasseV.Karlsen you are right, I find that I left out brackets outside the t2%2,which is not my original idea.When I add them up and test the function in my gcc by using (1+rand()%5) as rand5(), it works rightly. I fix my code and add up some explanation. – vvy Jun 19 '13 at 12:33
0

You need to use rejection sampling. That is, reject results that don't fit your target distribution. In your case you could use the lower three bits of two successive calls to your rand15 function (− 1 if necessary), concatenate them and reject those results that are outside your target interval and retry until you find a number that's inside.

Joey
  • 344,408
  • 85
  • 689
  • 683