CareerCup

The hard part is how to make sure the rand7() gives equally random probability.

The easiest way is to create a look-up table, where the table stores numbers from 1 to 7 with equal probability. And then think of a way to map rand5() results into the look-up table, with equal chance of mapping to any entry.

Thus, we can design a look-up table of size 5x5 as follow, where each number from 1 to 7 appears 3 times each:

Table = { 1, 1, 1, 2, 2,
		  2, 3, 3, 3, 4,
		  4, 4, 5, 5, 5,
		  6, 6, 6, 7, 7,
		  7, 8, 8, 8, 8
		}

Rand7() can be following:

rand7(){
	do{
		row = rand5() -1;
		col = rand5() -1;
		r7  = Table[row][col];
	} while (r7 > 7);

return r7;
}

We can see that row, col are equally likely between 0 to 4. Thus, each entry of the Table is chosen equally likely.
The loop condition while(r7>7) make sure that we only generate numbers from 1 to 7.

const int MAX = 5*5;
const int DIV = MAX/7;

int rand7()
{
    int num = (rand5()-1)*5+rand5()-1; // randomly distributed in 0:24
    return (num<MAX) ? (num/DIV) : rand7();
}

static int rand7()
{
var Input = new int[] { 1, 2, 3, 4, 5, 6, 7 };
var index = rand5();
while (CountNonZero(Input,7) > 1)
{
index += rand5();
index = index % 7;
if (Input[index] > 0)
Input[index] = 0;
else
{
while (Input[index] == 0)
{
index++;
index = index % 7;
}
Input[index] = 0;
if (CountNonZero(Input, 7) == 1)
break;
}
}
foreach (var v in Input)
if (v > 0) return v;
throw new NotImplementedException("something is wrong with rand7()!");
}

static private int CountNonZero(int[] input, int count)
{
var ret = 0;

foreach (var v in input)
if (v > 0) ret++;

return ret;
}

In Python :

import random

def rnd():
     r = random.randint(1, 7)
     return r

def rand2():
    toss = rand5()
    for i in range(100):
        if toss != 3:
            break
        toss = rand5()
    
    if toss < 3:
        return 1
    return 2

def rand7():
    x = 0
    for i in range(7):
        if rand2() == 1 :
            x += 3.5 / pow(2,i)
    return (int)(math.ceil(x))

def rand2():
    toss = rand5()
    for i in range(100):
        if toss != 3:
            break
        toss = rand5()
    
    if toss < 3:
        return 1
    return 2

def rand7():
    x = 0
    for i in range(7):
        if rand2() == 1 :
            x += 3.5 / pow(2,i)
    return (int)(math.ceil(x))

multiply the output of rand5() by 7/5

rand7() {
	int i = 0; sum = 0;
	while (i < 7) {
		sum += rand5();
	}
	return (sum / 5);
   }

int rand7() {
int i=0;sum=0;
while (i++ < 7) { sum+= rand5(); }
return (sum / 5);
}

Adding rand5() twice and modulus 7. if 0 then return 7 , since range should be between 1 - 7

static int rand7() {
	int r = (rand5() + rand5()) % 7;
	if (r == 0) {
		r = 7;
	}

	return r;
}

Hope you like this:

import random

def rand5():
	return random.randint(1,5)

def rand7():
	print random.randint(rand5(), 7)

rand7()

Have a binary array of 5x7 slots, and call the rand5 7 times, putting the result into the 1st, 2nd, etc 5-bit sub-array. This creates an equal distribution for all over the 35 slots, and if you think the other way (7-bit subarrays) the distribution is the same good (equal probablity) on those slots, too. So getting 7 values from rand5 will result in having 5 rand7 values in the array.

When a new rand7 value is needed get the number(s) from the 7-bit slots.
Do it 5 times - then all is used - so generate the array again.

Coding is left to the reader as an exercise :)

To ensure that the new function has a uniform distribution we can do this:

1) We are going to treat the 7 as a binary number 111
2) We are going to call rand5() for every single bit the seven has (3).
3) If the dice give us a {1,2} the bit is 0
If the dice give us a {3,4} the bit is 1
If the dice give us a 5 we call rand5() again.

4) If we end up with a 000 combination, we repeat the whole process because the result needs to be between 1 and 7.

This doesn't have a great performance, but I think this exercise cares more about the uniformity of the probability function than the execution time of it.

A person's first inclination would be to use the modulo operator. However, the problem with using the modulo operator here is you won't get a uniform distribution. Let's step through each scenario for rand5() % 4, for instance. 1%4 =1 2%4=2 3%4=3 4%4=0 5%4=1 . "1" is listed twice...meaning you're twice as likely to get a 1 than a 2 for instance.

An easy way to solve this problem is to find the least common multiple of 7 and 5, 35. You can then add rand5() seven times, and then you can modulo it with 7, knowing it will be uniform.

def rand7():
    return ( rand5() + rand5() +  rand5() +  rand5() +  rand5() +  rand5() +  rand5()  )  % 7

1. Draw 2 random numbers from rand5()
2. Add them. Possible outcome will be contained in set [2,3,4,...,10]
3. Map [2,3,4,...,8] --> [1,2,3,...,7] and reject [9,10]

Addition of two random variables will give a uniform distribution in the interval [2,3,..,8].
We are using this section to draw numbers from [1...7] uniformly.

I hope it's correct theoretically.

1. Draw 2 random numbers from rand5()
2. Add them. Possible outcome will be contained in set [2,3,4,...,10]
3. Map [2,3,4,...,8] --> [1,2,3,...,7] and reject [9,10]

Addition of two random variables will give a uniform distribution in the interval [2,3,..,8].
We are using this section to draw numbers from [1...7] uniformly.

I hope it's correct theoretically.

1. Draw 2 random numbers from rand5()
2. Add them. Possible outcome will be contained in set [2,3,4,...,10]
3. Map [2,3,4,...,8] --> [1,2,3,...,7] and reject [9,10]

Addition of two random variables will give a uniform distribution in the interval [2,3,..,8].
We are using this section to draw numbers from [1...7] uniformly.

I hope it's correct theoretically.

1. Draw 2 random numbers from rand5()
2. Add them. Possible outcome will be contained in set [2,3,4,...,10]
3. Map [2,3,4,...,8] --> [1,2,3,...,7] and reject [9,10]

Addition of two random variables will give a uniform distribution in the interval [2,3,..,8].
We are using this section to draw numbers from [1...7] uniformly.

I hope it's correct theoretically.

>>> from random import randint
>>> def f5(p1=5):
return randint(0,p1)
>>> def f7():
return f5(p1=7)

>>> from random import randint
>>> def f5(p1=5):
return randint(0,p1)

>>> def f7():
return f5(p1=7)

If you know rejection sampling...

import random
import matplotlib.pyplot as plt

def OneTwoThree():
    while True:
        x = random.randint(1,5)
        if x == 1 or x == 2 or x==3:
            return x
        
def rand7():
    while True:
        x = OneTwoThree()
        y = random.randint(1,5)
        if x == 1 or x == 2:
            return y
        if x == 3:
            if y == 1 or y == 2:
                return 6
            if y == 3 or y == 4:
                return 7
# Test
data = []
for i in range(100000):
    a = rand7()
    data.append(a)

plt.hist(data)
plt.show()

import random
import matplotlib.pyplot as plt

def OneTwoThree():
    while True:
        x = random.randint(1,5)
        if x == 1 or x == 2 or x==3:
            return x
        
def rand7():
    while True:
        x = OneTwoThree()
        y = random.randint(1,5)
        if x == 1 or x == 2:
            return y
        if x == 3:
            if y == 1 or y == 2:
                return 6
            if y == 3 or y == 4:
                return 7
# Test
data = []
for i in range(100000):
    a = rand7()
    data.append(a)

plt.hist(data)
plt.show()

def rand7():
  		return [1, 2 , 3, 4, 5, 6, 7][rand5() + rand5()*rand5()%3 - 1]

import numpy as np

def rand5():
return 1 + 4 * np.random.random(1)

def rand7():
return 1 + 6 * (rand5()-1)/4

import numpy as np

def rand5():
return 1 + 4 * np.random.random(1)

def rand7():
return 1 + 6 * (rand5()-1)/4

from random import randint

def rand5():
return randint(1,5)

def rand7():
a1 = rand5()
a2 = rand5()
a3 = rand5()
a4 = rand5()
a5 = rand5()
a6 = rand5()
a7 = rand5()
print(a1,a2,a3,a4,a5,a6,a7)
print(a1+a2+a3+a4+a5+a6+a7)
return int((a1+a2+a3+a4+a5+a6+a7)/7.0)

print(rand7())

from random import randint

def rand5():
  return randint(1,5)

def rand7():
  a1 =  rand5()
  a2 =  rand5()
  a3 =  rand5()
  a4 =  rand5()
  a5 =  rand5()
  a6 =  rand5()
  a7 =  rand5()
  return (a1+a2+a3+a4+a5+a6+a7)%7 +1

#QC : roughly equal probabilities
a1,a2,a3,a4,a5,a6,a7=0,0,0,0,0,0,0
for i in range(1,1002):
  x=rand7()
  if x == 1:
    a1 += 1
  elif x == 2:
    a2 += 1
  elif x == 3:
    a3 += 1
  elif x == 4:
    a4 += 1
  elif x == 5:
    a5 += 1
  elif x == 6:
    a6 += 1
  elif x == 7:
    a7 += 1

print(a1,a2,a3,a4,a5,a6,a7)

Use rand5() 7 times, take the sum and then mod 7. This gives us rand7()

int rand7()
{
const int MAX = 5*5;
const int DIV = MAX/7;
int num = 5*(rand5()-1)+rand5()-1; // randomly distributed within 0:24
if(num < MAX)
return (num/div)+1;
else
return rand7();
}

const int MAX = 5*5;
const int DIV = MAX/7;

int rand7()
{
    int num = (rand5()-1)*5+rand5()-1; // randomly distributed in 0:24
    return (num<MAX) ? (num/DIV) : rand7();
}

Do rand(5) up to 7 times.

1. rand(5) -> if it is 1, return 1.
2. rand(5) -> if it is 1, return 2.
3. rand(5) -> if it is 1, return 3.
4. rand(5) -> if it is 1, return 4.
5. rand(5) -> if it is 1, return 5.
6. rand(5) -> if it is 1, return 6.
7. rand(5) -> if it is 1, return 7.

Double rand7(){
Double a = rand5() +2.0

return a
}

double Rand7()
{
	return (rand5()/5)*7
}

random5()+(random5())%3

random5()+(random5())%3

{random5()+(random5())%3}

rand7= (rand5()/5)*7