**Question: **Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. The distribution between each of the numbers must be uniform.

**Challenge:** Do you know the answer to this question? Post in the comments. Let’s see who is **up for the challenge**. Answers will be posted **February 26th**.

Let’s think of this like a decision tree. Each rand5() will be a decision. After 2 tries, we have 25 possible solutions. We try to get maximum bunches of 7 as we can (1 – 21, 3 sets of 7). If we get any of the other values, we just try again. Since the probability of getting each of 21 values are the same every time, trying again won’t affect their probabilities.

int rand7() { while (1) { int num = 5*(rand5()-1) + rand5(); if (num < 22) return ((num % 7) + 1); } }

That was fun, right? Anyone up for another challenge? Watch out for it next tuesday (March 1st).

**If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:**

= rand5()*1 + rand5()*2 + rand5()*4

Apologies for the error in the previous post. Should be this…

Create an array ‘a’ of 5 x 7 = 35 elements and populate it with 5 sets of 1 through 7.

So we have something like

1 2 3 4 5

6 7 1 2 3

4 5 6 7 1

2 3 4 5 6

7 1 2 3 4

5 6 7 1 2

3 4 5 6 7

Hold the state as ‘s’ = 0;

So for each call the random number would be

a[((s++ % 7) * 5) + Rand5() – 1]

If necessary allow ‘s’ to be set initially as a seed value.

this is easy, generate 7 random numbers between 1-5, add them together and divide by five. Then round that number down and you will get a equally distributed number between 1-7. To further explain

if you add 7 random numbers between 1-5 you will get a sum of 7 – 35. If you then divide that sum by 5 you will received a result of 1.4 – 7 which when rounded down will give you an equal distribution of numbers between 1-7.

As 7 doesn’t divide 5^k for any integer k, a uniformly selected number between 1 and 7 can not be generated by a finite number of calls to rand_1_5(). However, an algorithm can be constructed so that it will terminate with probability 1.

A simple solution would be something like

int rand_1_7() {

int random;

do {

random = (rand_1_5() - 1) * 5 + (rand_1_5() - 1);

} while (random >= 21);

return random % 7 + 1;

}

If rand_1_5() is a slow function, we can make an effort into not not wasting entropy obtained from it.

int rand_1_7() {

int cur = 0;

int max = 1;

do {

do {

cur = cur * 5 + rand_1_5() - 1;

max *= 5;

} while (max < 7);

if (cur < (max/7)*7) {

return (cur%7)+1;

} else {

cur = cur % 7;

max = max % 7;

}

} while (1);

}

It requires slightly fewer calls to rand_1_5() (about 2.21 on average, instead of 2.38).

s = rand1to5*5+rand1to5;

if s < 27 then x = s mod 7;

else return;

I think the simplest solution is to work out a 2-digit number in base 5 (value from 0 to 24). We have three uniform-distribution blocks of seven in that space, and an ugly end-bit. So if the value is in the ugly end bit (21-24) just drop it and try again.

I haven’t got a formal proof but this should provide a uniform distrubution:

while (true) {

int n=(random5() * 5) + random5() – 6; // 0 to 24

if (n<21) return (n%7) + 1; // 1 to 7

} // Loop until we hit a good value

Is it given that the function returning a random number between 1 and 5 does so with uniform distribution?

If so then the following works by scaling it up so keeping the given distribution:

def rand1to7

return (1.5 * (rand1to5 - 1)) + 1

end

some_func(){

tmp = 0

tmp += random5() foreach 0:7

return tmp%7

}

Create an array ‘a’ of 5 x 7 = 35 elements and populate it with 5 sets of 1 thru 7.

So we have something like

1 2 3 4 5

6 7 1 2 3

4 5 6 7 1

2 3 4 5 6

7 1 2 3 4

5 6 7 1 2

3 4 5 6 7

Hold the state as ‘s’ = 0;

So for each call the random number would be

a[(s++ % 7) + Rand5() – 1]

If necessary allow s to be used as a seed value.

Create an array ‘a’ of 5 x 7 = 35 elements and populate it with 5 sets of 1 through 7.

So we have something like

1 2 3 4 5

6 7 1 2 3

4 5 6 7 1

2 3 4 5 6

7 1 2 3 4

5 6 7 1 2

3 4 5 6 7

Hold the state as ‘s’ = 0;

So for each call the random number would be

a[(s++ % 7) + Rand5() – 1]

If necessary allow s to be used as a seed value.

int result;

do {

result = 0;

result += (rand1to5() – 1); // first two bits, uniform

tmp = 0;

do {tmp = rand1to5(); } while(tmp == 5); //

result += (tmp % 2 << 3) + 1;

} while(result == 8);

In the method below, each number competes in a round robin twice. The competing numbers use Rand5 mod 2. Because Rand5 favors the odd number, two loops are performed. The first one favors the inner loop, the second favors the outer loop. Each number will compete 12 times until there is a clear winner.

Public Function Random7() As Integer

Dim oRand As New Random()

Dim iArray(6) As Integer

Dim iIndex As Integer = -1

Dim iValue As Integer = -1

While iIndex = -1

Array.Clear(iArray, 0, iArray.Length)

iIndex = -1

iValue = -1

For i As Integer = 0 To 5

For j As Integer = i + 1 To 6

iArray(IIf(m_oRand.Next(1, 6) Mod 2 = 0, i, j)) += 1

Next j

Next i

For i As Integer = 0 To 5

For j As Integer = i + 1 To 6

iArray(IIf(m_oRand.Next(1, 6) Mod 2 = 1, i, j)) += 1

Next j

Next i

For i As Integer = 0 To 6

If iArray(i) = iValue Then

iIndex = -1

ElseIf iArray(i) > iValue Then

iValue = iArray(i)

iIndex = i

End If

Next i

End While

Return iIndex + 1

End Function

Chris Lamont’s is equivalent to mine.

Requires about 2.4 evals of random 1..5 to get

random 1..7. One could get it down to about 2.2 evals by not throwing away the randomness of the generated cases that flunk the filter.

He posted first, but I wrote mine at work and had to come home to post it, and I didn’t really look hard at any of the other entries before I did. Great minds think alike.

import random

answerMap = { (1, 1): 1,

(1, 2): 2,

(1, 3): 3,

(1, 4): 4,

(1, 5): 5,

(2, 1): 6,

(2, 2): 7,

(2, 3): 1,

(2, 4): 2,

(2, 5): 3,

(3, 1): 4,

(3, 2): 5,

(3, 3): 6,

(3, 4): 7,

(3, 5): 1,

(4, 1): 2,

(4, 2): 3,

(4, 3): 4,

(4, 4): 5,

(4, 5): 6,

(5, 1): 7 }

def rand15():

return random.randint(1, 5)

def rand17():

global answerMap

randPair = (rand15(), rand15())

if answerMap.has_key(randPair):

return answerMap[randPair]

else:

return rand17()

tallies = [0, 0, 0, 0, 0, 0, 0]

for i in range(1000000):

tallies[rand17() – 1] += 1

print tallies

the issue laid on equal probability distribution between [1..7]. Assuming rand_5() is the function to generate number [1..5] and we repeat this function X times and get a sum value, so the possible sum value will be from X to 5X and it is still a equal distribution, then if the total number of possible values between X and 5X can be divided by 7, then the problem is resovled. So we are just looking at this equation:

5*X - X + 1 = 7 * y

it is not difficult to figure out a combination:

X = 5 ; Y = 3

so the function is

function rand_7() {

return (rand_5() + rand_5() + rand_5() + rand_5() + rand_5() - 2) / 3

}

Here’s a very unusual one that has very even distribution. I’m warning you, it may make you angry.

int get1_7()

{

static bool first = true;

static std::vector a;

if ( first )

{

first = false;

for ( int i = 0; i < 7; ++i )

a.push_back(i+1);

for ( int i = 0; i < 7; ++i )

get1_7();

}

int i = get1_5();

int r = a[i-1];

a.push_back( r );

a.erase(a.begin()+i-1);

return r;

}

def rand7():

n = sum(value * 5 ** index for (index, value) in enumerate([rand5(), rand5(), rand5(), rand5(), rand5(), rand5()]))

if n == 0:

return rand7()

else:

return 1 + n % 7

Since the indentation gets all screwed up, I made it easier to read.

#define f rand15()

#define s switch

#define c case

#define d default

#define o rand01()

#define r return

#define w while

int o{s(f){c 1:c 2:r 0;c 3:c 4:r 1;d: r o;}}

int rand17(){int t=0;do{t=o|o<<1|o<<2;}w(t==0);r t;}

Wateful, but correct:

int rand01()

{

switch(rand15()) {

case 1: case 2: return 0 ;

case 3: case 4: return 1 ;

default: return rand01() ;

}

}

`int rand17()`

{

int tmp = 0 ;

do { tmp = rand01() | rand01() << 1 | rand01() << 2 ; } while(tmp == 0) ;

return tmp ;

}

(The commenting system ate the indentation above, even though it was inside code tags).

This gives a good distribution for me (it’s in Python):

`>>> import random`

>>> list5 = range(1,6)

>>> def rand5(): return random.choice(list5)

>>> def rand7():

return (sum(rand5() for x in range(7)) % 7) + 1

>>> bin = dict((x, 0) for x in range(1,8))

>>> bin

{1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0}

>>> for i in range(700000):

bin[rand7()] += 1

`>>> bin`

{1: 100282, 2: 100464, 3: 99527, 4: 99995, 5: 99962, 6: 100081, 7: 99689}

– Paddy.

Oops. My previous attempt was in error. 1..4 have probability 4/25 of showing up, 5..5 have probability 3/25 of showing up. My bad. How about

do {

int rand_0_24 = (rand5() – 1) + 5 * (rand5() – 1)

rand7 = 1 + rand_0_24

while (rand7 > 7)

n.b. the order of 5 mod 7 is 6.

int rand7()

{

int sum, i;

do

{

sum=0;

for (i=0; i<6; i++)

sum = 5*sum+(rand5()-1);

}

while (sum==0);

`return 1+sum%7;`

}

int rand_0_24 = (rand5() – 1) + 5 * (rand5() – 1)

rand7 = 1 + (rand_0_24) % 7

@Chris Lomont:

(rand5() – 1)*6/4 still produces a total range of 5 distinct numbers, it does not generate all 7 numbers in the desired output range.

@mikeash: I like your rand5() + 5 * (rand5() – 1) solution. At first I didn’t think it was uniform until I looked more closely. The rest is more or less what I did earlier (re-rolling if you get a certain number).

@Anonymous: rand5() + rand5() is not a uniform distribution from 2 to 10. It’s a triangle distribution.

First create an evenly distributed distributed random number from 1-25:

int rand25(void) {

return rand5() + 5 * (rand5() - 1);

}

Now use it to generate a random number from 1-7. For efficiency, I accept the range 1-21 and divide it by 3 to get 1-7. In the range 22-25, retry:

int rand7(void) {

int n = rand25();

return n <= 21 ? n / 3 : rand7();

}

Thanks Doggie! I think it was implied as well, but a lot of people (from looking at previous comments) seem to conflate ‘randomness’ with ‘uniform distribution’.

(rand5()-1)*6/4+1 works, except you probably want a random *integer* between 1 and 7. Then roll and discard works perfectly fine, treating rand rolls as base 5 digits:

do {

val = 5*(rand5-1)+(rand5-1) // in 0-24 uniformly.

} while val >20;

// now in 0-20 uniformly

return (val%7)+1; //

Doing this for more digits may lower expected running time, for example using three rolls as three base 5 digits, and converting to base 7, re-rolling on values above the n-digit cutoff.

int rand7() {

int bits12 = rand5() & 3;

int bits34 = rand5() & 3;

return bits12 + (bits34 << 2);

}

int rand7() {

int n;

/* make a uniform distribution from 2 to 10, shift down to 1 to 9, and chop off the top 2 values by re-rolling if you’re above 7 */

do {

n = (rand5() + rand5() – 1);

} while (n > 7);

return n;

}

I think the uniform distribution is implied but if it wasn’t clear, I will just add that to the question.

Since you didn’t specify a uniform distribution requirement in the body of your challenge, you can simply take a random number from [1..5] and return that as your random number between [1..7].

I’m sure someone’s already said that but I haven’t read the comments, as I’m working the proper answer out myself and don’t want to get spoilt 😛

Another evenly distributed solution is to just roll the die twice. If you roll 11, 12, 13, or 14 erase the result and roll both times again. Repeat until you get something that is not 11, 12, 13, or 14. Then perform the following mapping:

15,21,22 -> return 1

23,24,25 -> return 2

31,32,33 -> return 3

34,35,41 -> return 4

42,43,44 -> return 5

45,51,52 -> return 6

53,54,55 -> return 7

@Zach My calculator played tricks on me. You are absolutely correct, shame on me.

@dschooh: 5 and 7 are co-prime. The number of outcomes of rolling a 5 sided die is always a power of 5. In this case, 5^13, which is not divisible by 7. Where are you getting 174,386,161?

Ok it totally butchered my code sample. Don’t know what that’s about.

Anyway the idea is this:

Keep trying this algorithm until the number is from 1 to 7. The algorithm is this:

1) Keep trying to generate a number that’s either 1 or 2, when you do subtract 1 to get either 0 or 1, and use that as the next “bit” in the bit representation of a number.

2) Do this 3 times. One for the 0’th (rightmost) bit, one for the first bit, and one for the second bit.

3) The end result of this is an evenly distributed number from 0 to 7. But the original loop will just try again if you have 0, ending up with a number from 1 to 7.

No solution that involves addition will work, period. In fact, if you’re combining the results of the rand functions at all the solution is highly suspicious. The reason is that these combinations do not generally maintain an even distribution.

Take addition for example.

rand_15() + rand_15().

This will generate two evenly distributed numbers from 1 to 5, add them together, to generate a “random” number from 2 to 10. But this distribution is nowhere near even. In fact, it’s a triangle distrubtion. There’s only 1 possible way to generate the number 2 (1+1) but there are 5 ways to generate the number 6 (1+5, 5+1, 2+4, 4+2, 3+3).

So, if you’re proposing addition, throw it out the water because it doesn’t work.

The only foolproof way I can think of so far to generate an even distribution is this:

int rand7()

{

unsigned result = 0;

int temp = 0;

while (result == 0)

{

for (int i=0; i 2);

//Scale it to 0 or 1

--temp;

//Set the next bit in the result

result |= (temp << i);

}

`//Now that we've set bits 0, 1, and 2, we have a number from 0 to 7`

//We need a number from 1 to 7, but the outer while loop will just try

//again if we have 0. The end result is a number from 1 to 7

}

}

Idea: Throw 13 5-sided dices, which will have 174,386,161 possible outcomes, which in turn can be devided by 7 and such can be evenly distributed through 1 to 7.

randoms = []

13.times do

randoms.push(rand(5) + 1)

end

result = 0

randoms.each_with_index do |x, i|

result += x * (5 ** i)

end

`puts result % 7 + 1`

Sorry, y in the for loop should be defined as 0.1.

My solution generates a float in base five between [0,1), and uses that to calculate the random integer between [1,7]. This should be as random and evenly distributed as the generator of [1,5], but no more.

float baseFive = 0;

for(float y = 0; y>0; y = y/10)

{

baseFive += rand5() * y;

}

float baseTen = fromBaseFive(baseFive);

return ((int)(7*baseTen)) +1;

`random1to7=function(){`

`return 1+(random1to5()+random1to5()+random1to5()+random1to5()+random1to5()+random1to5()+random1to5())%7`

}

Well the function that returns 1 – 5 by default is returning numbers between 1 and 7, it just will not return 6 and 7.

Hmm, must the answer be guaranteed to terminate in some definite time bound? Or is it sufficient to terminate with probability 1? If the latter, then the question is not difficult. If the former, I haven’t figured it out yet.

My first attempt would look like this:

int x = 0;

for(int i = 0; i < 7; ++i)

x += randombetween1and5();

return (x mod 7) + 1;

There is a problem with this approach though. This is not an even distribution. Out of the possible results for x mod 7, 0 through 6, 0 will be a possible result 1 more time than any other value.

I don’t think the above solutions generate a prob density function that is even across 1-7- in order for it to be truly random each number needs to be equally probable. If you roll the random number generator 6 times (to get a max number that is a multiple of 5 and 7) mod 7 the odds should be evenly distributed rather than favoring some numbers.

inclusive

Is the between 1 and 5/7 inclusive or exclusive?

3/2 * ( random1_5() – 1 ) + 1

Function RandomBetween1And5() As Integer

Return (some number)

End Function

Function RandomBetween1And7() As Integer

Return 1 + ((RandomBetween1And5() + RandomBetween1And5()) Mod 6)

End Function