Расширить случайный диапазон от 1–5 до 1–7
Для данной функции, которая выдает случайное целое число в диапазоне от 1 до 5, напишите функцию, которая выдает случайное целое число в диапазоне от 1 до 7.
- Что такое простое решение?
- Каково эффективное решение для уменьшения использования памяти или работы на более медленном процессоре?
80 ответов
Это эквивалентно решению Адама Розенфилда, но может быть немного более понятным для некоторых читателей. Предполагается, что rand5() - это функция, которая возвращает статистически случайное целое число в диапазоне от 1 до 5 включительно.
int rand7()
{
int vals[5][5] = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 1, 2, 3 },
{ 4, 5, 6, 7, 1 },
{ 2, 3, 4, 5, 6 },
{ 7, 0, 0, 0, 0 }
};
int result = 0;
while (result == 0)
{
int i = rand5();
int j = rand5();
result = vals[i-1][j-1];
}
return result;
}
Как это работает? Подумайте об этом так: представьте себе распечатку этого массива двойного размера на бумаге, прикрепление его к доске для дротиков и случайное бросание в нее дротиков. Если вы нажмете ненулевое значение, это статистически случайное значение от 1 до 7, так как есть равное число ненулевых значений на выбор. Если вы попали в ноль, просто продолжайте бросать дротик, пока не достигнете ненулевого значения. Вот что делает этот код: индексы i и j случайным образом выбирают место на доске для дротиков, и если мы не получаем хорошего результата, мы продолжаем бросать дротики.
Как сказал Адам, в худшем случае это может продолжаться вечно, но статистически наихудшего случая никогда не бывает.:)
Не существует (абсолютно правильного) решения, которое будет выполняться за постоянное количество времени, поскольку 1/7 - это бесконечное десятичное число в базе 5. Одним из простых решений будет использование выборки отклонения, например:
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7
Ожидаемое время выполнения составляет 25/21 = 1,19 итераций цикла, но существует бесконечно малая вероятность зацикливания навсегда.
Я хотел бы добавить еще один ответ, в дополнение к моему первому ответу. Этот ответ пытается минимизировать количество звонков rand5() за звонок rand7(), чтобы максимально использовать случайность. То есть, если вы считаете случайность ценным ресурсом, мы хотим использовать как можно большую ее часть, не выбрасывая случайные биты. Этот ответ также имеет некоторые сходства с логикой, представленной в ответе Ивана.
Энтропия случайной величины является четко определенной величиной. Для случайной величины, которая принимает N состояний с равными вероятностями (равномерное распределение), энтропия равна log 2 Н. Таким образом, rand5() имеет приблизительно 2.32193 бита энтропии, и rand7() имеет около 2,80735 бит энтропии. Если мы надеемся максимизировать наше использование случайности, нам нужно использовать все 2.32193 бита энтропии при каждом обращении к rand5() и применять их для генерации 2,80735 битов энтропии, необходимых для каждого вызова rand7(), Таким образом, фундаментальный предел заключается в том, что мы можем делать не лучше, чем log(7)/log(5) = 1.20906 вызовов rand5() за звонок rand7(),
Примечания: все логарифмы в этом ответе будут основанием 2, если не указано иное. rand5() предполагается, что будут возвращаться числа в диапазоне [0, 4], и rand7() предполагается, что будут возвращаться числа в диапазоне [0, 6]. Настройка диапазонов на [1, 5] и [1, 7] соответственно тривиальна.
Так как нам это сделать? Мы генерируем бесконечно точное случайное действительное число от 0 до 1 (представьте, что мы действительно можем вычислить и сохранить такое бесконечно точное число - мы исправим это позже). Мы можем генерировать такое число, генерируя его цифры в базе 5: мы выбираем случайное число 0. a 1 a 2 a 3..., где каждая цифра i выбирается звонком rand5(), Например, если наш RNG выбрал i = 1 для всех i, затем игнорируя тот факт, что это не очень случайно, это будет соответствовать действительному числу 1/5 + 1/5 2 + 1/5 3 +... = 1/4 (сумма геометрического ряда).
Итак, мы выбрали случайное действительное число от 0 до 1. Теперь я утверждаю, что такое случайное число распределено равномерно. Интуитивно понятно, что это легко понять, поскольку каждая цифра выбрана одинаково, а число является бесконечно точным. Однако формальное доказательство этого несколько сложнее, поскольку теперь мы имеем дело с непрерывным распределением, а не с дискретным, поэтому нам нужно доказать, что вероятность того, что наше число лежит в интервале [ a, b ] равна длине этого интервала, b - a, Доказательство оставлено в качестве упражнения для читателя =).
Теперь, когда у нас есть случайное действительное число, выбранное равномерно из диапазона [0, 1], нам нужно преобразовать его в серию равномерно случайных чисел в диапазоне [0, 6], чтобы сгенерировать вывод rand7(), как нам это сделать? Как раз наоборот, что мы только что сделали - мы конвертируем его в бесконечно точное десятичное число в базе 7, и тогда каждая цифра в базовой 7 будет соответствовать одному выходу rand7(),
Принимая пример из ранее, если наш rand5() производит бесконечный поток 1, тогда наше случайное действительное число будет 1/4. Преобразовав 1/4 в основание 7, мы получим бесконечное десятичное число 0,15151515..., поэтому мы будем производить в качестве выходных 1, 5, 1, 5, 1, 5 и т. Д.
Итак, у нас есть основная идея, но у нас осталось две проблемы: мы не можем на самом деле вычислить или сохранить бесконечно точное действительное число, так как же нам иметь дело только с его конечной частью? Во-вторых, как мы на самом деле конвертируем его в базу 7?
Один из способов преобразования числа от 0 до 1 в основание 7 заключается в следующем:
- Умножить на 7
- Неотъемлемой частью результата является следующая базовая 7 цифра
- Вычтите неотъемлемую часть, оставив только дробную часть
- Перейти к шагу 1
Чтобы справиться с проблемой бесконечной точности, мы вычисляем частичный результат и также сохраняем верхнюю границу того, каким может быть результат. То есть предположим, что мы позвонили rand5() дважды, и он возвратился 1 оба раза. Число, которое мы сгенерировали до сих пор, составляет 0,11 (основание 5). Какими бы ни были остальные бесконечные серии призывов к rand5() производим, случайное действительное число, которое мы генерируем, никогда не будет больше 0,12: всегда верно, что 0,11 ≤ 0,11xyz... < 0,12.
Таким образом, отслеживая текущее число и максимальное значение, которое оно может принять, мы конвертируем оба числа в основание 7. Если они согласны с первым k цифры, то мы можем спокойно вывести следующий k цифры - независимо от того, что представляет собой бесконечный поток из базовых 5 цифр, они никогда не будут влиять на следующую k цифры базового 7 представления!
И это алгоритм - генерировать следующий вывод rand7() мы генерируем только столько цифр rand5() так как нам нужно убедиться, что мы точно знаем значение следующей цифры при преобразовании случайного действительного числа в основание 7. Вот реализация Python с тестовым набором:
import random
rand5_calls = 0
def rand5():
global rand5_calls
rand5_calls += 1
return random.randint(0, 4)
def rand7_gen():
state = 0
pow5 = 1
pow7 = 7
while True:
if state / pow5 == (state + pow7) / pow5:
result = state / pow5
state = (state - result * pow5) * 7
pow7 *= 7
yield result
else:
state = 5 * state + pow7 * rand5()
pow5 *= 5
if __name__ == '__main__':
r7 = rand7_gen()
N = 10000
x = list(next(r7) for i in range(N))
distr = [x.count(i) for i in range(7)]
expmean = N / 7.0
expstddev = math.sqrt(N * (1.0/7.0) * (6.0/7.0))
print '%d TRIALS' % N
print 'Expected mean: %.1f' % expmean
print 'Expected standard deviation: %.1f' % expstddev
print
print 'DISTRIBUTION:'
for i in range(7):
print '%d: %d (%+.3f stddevs)' % (i, distr[i], (distr[i] - expmean) / expstddev)
print
print 'Calls to rand5: %d (average of %f per call to rand7)' % (rand5_calls, float(rand5_calls) / N)
Обратите внимание, что rand7_gen() возвращает генератор, так как он имеет внутреннее состояние, включающее преобразование числа в основание 7. Тестирование вызывает next(r7) 10000 раз, чтобы произвести 10000 случайных чисел, а затем он измеряет их распределение. Используется только целочисленная математика, поэтому результаты в точности верны.
Также обратите внимание, что числа здесь становятся очень большими, очень быстрыми. Способности 5 и 7 растут быстро. Следовательно, производительность начнет заметно ухудшаться после генерации большого количества случайных чисел из-за арифметики Бигнума. Но помните здесь, моя цель состояла в том, чтобы максимально использовать случайные биты, а не максимизировать производительность (хотя это вторичная цель).
За один прогон я сделал 12091 звонок rand5() на 10000 звонков rand7() при достижении минимума вызовов log (7) / log (5) в среднем до 4 значащих цифр, и полученный результат был однородным.
Чтобы перенести этот код на язык, который не имеет встроенных произвольно больших целых чисел, вам нужно ограничить значения pow5 а также pow7 к максимальному значению вашего собственного целочисленного типа - если они становятся слишком большими, то сбросьте все и начните все сначала. Это увеличит среднее количество звонков на rand5() за звонок rand7() очень незначительно, но, надеюсь, оно не должно увеличиваться слишком сильно даже для 32- или 64-разрядных целых чисел.
(Я украл ответ Адама Розенфельда и заставил его работать примерно на 7% быстрее.)
Предположим, что rand5() возвращает один из {0,1,2,3,4} с равным распределением, и цель - вернуть {0,1,2,3,4,5,6} с равным распределением.
int rand7() {
i = 5 * rand5() + rand5();
max = 25;
//i is uniform among {0 ... max-1}
while(i < max%7) {
//i is uniform among {0 ... (max%7 - 1)}
i *= 5;
i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
max %= 7;
max *= 5; //once again, i is uniform among {0 ... max-1}
}
return(i%7);
}
Мы отслеживаем наибольшее значение, которое цикл может сделать в переменной max, Если результат пока находится между max%7 и max-1, то результат будет равномерно распределен в этом диапазоне. Если нет, мы используем остаток, который является случайным между 0 и max%7-1, и еще один вызов rand() для создания нового числа и нового максимума. Тогда мы начнем снова.
Изменить: Ожидайте, сколько раз вызов rand5() равен x в этом уравнении:
x = 2 * 21/25
+ 3 * 4/25 * 14/20
+ 4 * 4/25 * 6/20 * 28/30
+ 5 * 4/25 * 6/20 * 2/30 * 7/10
+ 6 * 4/25 * 6/20 * 2/30 * 3/10 * 14/15
+ (6+x) * 4/25 * 6/20 * 2/30 * 3/10 * 1/15
x = about 2.21 calls to rand5()
Алгоритм:
7 может быть представлен в последовательности из 3 бит
Используйте rand(5), чтобы случайным образом заполнить каждый бит 0 или 1.
Например: позвоните rand(5) и
если результат равен 1 или 2, заполните бит 0
если результат равен 4 или 5, заполните бит 1
если результат равен 3, тогда проигнорируйте и сделайте это снова (отклонение)
Таким образом, мы можем произвольно заполнить 3 бита 0/1 и получить число от 1 до 7.
РЕДАКТИРОВАТЬ: кажется, самый простой и эффективный ответ, поэтому вот код для этого:
public static int random_7() {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + random_5_output_2();
}
}
return returnValue;
}
private static int random_5_output_2() {
while (true) {
int flip = random_5();
if (flip < 3) {
return 0;
}
else if (flip > 3) {
return 1;
}
}
}
int randbit( void )
{
while( 1 )
{
int r = rand5();
if( r <= 4 ) return(r & 1);
}
}
int randint( int nbits )
{
int result = 0;
while( nbits-- )
{
result = (result<<1) | randbit();
}
return( result );
}
int rand7( void )
{
while( 1 )
{
int r = randint( 3 ) + 1;
if( r <= 7 ) return( r );
}
}
rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1
Изменить: это не совсем работает. Это примерно на 2 части из 1000 (при условии идеального ранда5). Ведра получают:
value Count Error%
1 11158 -0.0035
2 11144 -0.0214
3 11144 -0.0214
4 11158 -0.0035
5 11172 +0.0144
6 11177 +0.0208
7 11172 +0.0144
Переходя на сумму
n Error%
10 +/- 1e-3,
12 +/- 1e-4,
14 +/- 1e-5,
16 +/- 1e-6,
...
28 +/- 3e-11
кажется, получает порядок величины для каждых 2 добавленных
Кстати, приведенная выше таблица ошибок была сгенерирована не с помощью выборки, а с помощью следующего отношения повторения:
p[x,n]это число способовoutput=xможет произойти, учитываяnзвонки вrand5,
p[1,1] ... p[5,1] = 1
p[6,1] ... p[7,1] = 0
p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1]
p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1]
p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1]
p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1]
p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1]
p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1]
p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1]
int ans = 0;
while (ans == 0)
{
for (int i=0; i<3; i++)
{
while ((r = rand5()) == 3){};
ans += (r < 3) >> i
}
}
int rand7() {
int value = rand5()
+ rand5() * 2
+ rand5() * 3
+ rand5() * 4
+ rand5() * 5
+ rand5() * 6;
return value%7;
}
В отличие от выбранного решения, алгоритм будет работать в постоянное время. Однако он делает на 2 вызова больше, чем среднее время выполнения выбранного решения.
Обратите внимание, что этот генератор не идеален (число 0 имеет на 0,0064% больше шансов, чем любое другое число), но для большинства практических целей гарантия постоянного времени, вероятно, перевешивает эту неточность.
объяснение
Это решение основано на том факте, что число 15 624 делится на 7, и, таким образом, если мы можем случайным образом и равномерно генерировать числа от 0 до 15 624, а затем взять мод 7, мы можем получить почти равномерный генератор rand7. Числа от 0 до 15 624 можно сгенерировать равномерно, выполнив rand5 6 раз и используя их для формирования цифр базового числа 5 следующим образом:
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
Свойства мода 7, однако, позволяют немного упростить уравнение:
5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7
Так
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
становится
rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5
теория
Число 15 624 не было выбрано случайно, но его можно обнаружить с помощью маленькой теоремы Ферма, которая утверждает, что если p - простое число, то
a^(p-1) = 1 mod p
Так что это дает нам,
(5^6)-1 = 0 mod 7
(5 ^ 6) -1 равно
4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4
Это число в форме основания 5, и поэтому мы можем видеть, что этот метод может использоваться для перехода от любого генератора случайных чисел к любому другому генератору случайных чисел. Хотя при использовании показателя степени p-1 всегда вводится небольшое смещение в сторону 0.
Ниже приводится равномерное распределение в {1, 2, 3, 4, 5, 6, 7} с использованием генератора случайных чисел, создающего равномерное распределение в {1, 2, 3, 4, 5}. Код грязный, но логика понятна.
public static int random_7(Random rg) {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + SimulateFairCoin(rg);
}
}
return returnValue;
}
private static int SimulateFairCoin(Random rg) {
while (true) {
int flipOne = random_5_mod_2(rg);
int flipTwo = random_5_mod_2(rg);
if (flipOne == 0 && flipTwo == 1) {
return 0;
}
else if (flipOne == 1 && flipTwo == 0) {
return 1;
}
}
}
private static int random_5_mod_2(Random rg) {
return random_5(rg) % 2;
}
private static int random_5(Random rg) {
return rg.Next(5) + 1;
}
Здесь разрешены проблемы с домашними заданиями?
Эта функция выполняет грубую математику "основание 5" для генерации числа от 0 до 6.
function rnd7() {
do {
r1 = rnd5() - 1;
do {
r2=rnd5() - 1;
} while (r2 > 1);
result = r2 * 5 + r1;
} while (result > 6);
return result + 1;
}
Если мы рассмотрим дополнительное ограничение попытки дать наиболее эффективный ответ, т.е. тот, который дал входной поток, Iравномерно распределенных целых чисел длины m из 1-5 выводит поток Oравномерно распределенных целых чисел от 1 до 7 самой длинной длины относительно m, сказать L(m),
Простейший способ проанализировать это - обработать потоки I и O как 5-арные и 7-арные числа соответственно. Это достигается за счет идеи основного ответа о взятии потока a1, a2, a3,... -> a1+5*a2+5^2*a3+.. и аналогично для потока O,
Тогда, если мы возьмем часть входного потока длины m choose n s.t. 5^m-7^n=c где c>0 и как можно меньше. Тогда есть однородная карта из входного потока длиной m в целые числа из 1 в 5^m и еще одна равномерная карта от целых чисел от 1 до 7^n к выходному потоку длины n, где мы можем потерять несколько случаев из входного потока, когда отображаемое целое число превышает 7^n,
Так что это дает значение для L(m) вокруг m (log5/log7) что примерно .82m,
Трудность с приведенным выше анализом заключается в уравнении 5^m-7^n=c что нелегко решить точно, и случай, когда равномерное значение из 1 в 5^m превышает 7^n и мы теряем эффективность.
Вопрос в том, насколько близко может быть достигнуто наилучшее возможное значение m (log5/log7). Например, когда это число приближается к целому числу, можем ли мы найти способ достижения этого точного целого числа выходных значений?
Если 5^m-7^n=c затем из входного потока мы эффективно генерируем равномерное случайное число из 0 в (5^m)-1 и не используйте значения выше 7^n, Однако эти значения могут быть восстановлены и использованы снова. Они эффективно генерируют единую последовательность чисел от 1 до 5^m-7^n, Таким образом, мы можем затем попытаться использовать их и преобразовать их в 7-разрядные числа, чтобы мы могли создать больше выходных значений.
Если мы позволим T7(X) быть средней длиной выходной последовательности random(1-7) целые числа, полученные из равномерного ввода размера Xи предполагая, что 5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7,
затем T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0) так как у нас нет длины без последовательности с вероятностью 7^n0/5^m с остатком длины 5^m-7^n0 с вероятностью (5^m-7^n0)/5^m),
Если мы просто продолжим замену, мы получим:
T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m
следовательно
L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s)
Другой способ выразить это:
If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r
Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r)
Наилучший возможный случай - мой оригинальный, где 5^m=7^n+s, где s<7,
затем T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1) как прежде.
Худший случай, когда мы можем найти только k и st 5^m = kx7+s.
Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1)
Другие случаи находятся где-то посередине. Было бы интересно посмотреть, насколько хорошо мы можем сделать для очень большого m, т.е. насколько хорошо мы можем получить термин ошибки:
T7(5^m) = m (Log5/Log7)+e(m)
Кажется невозможным достичь e(m) = o(1) в общем но надеюсь мы сможем доказать e(m)=o(m),
Тогда все дело в распределении 7-ми цифр 5^m для различных значений m,
Я уверен, что есть много теории, которая покрывает это, я могу взглянуть и доложить в какой-то момент.
Вот рабочая реализация ответа Адама на Python.
import random
def rand5():
return random.randint(1, 5)
def rand7():
while True:
r = 5 * (rand5() - 1) + rand5()
#r is now uniformly random between 1 and 25
if (r <= 21):
break
#result is now uniformly random between 1 and 7
return r % 7 + 1
Мне нравится бросать алгоритмы, которые я рассматриваю, в Python, чтобы я мог поиграть с ними, подумал, что я опубликую это здесь в надежде, что это будет полезно для кого-то там, а не то, что это заняло много времени, чтобы бросить вместе.
Почему бы не сделать это просто?
int random7() {
return random5() + (random5() % 3);
}
Шанс получить 1 и 7 в этом решении ниже по модулю, однако, если вы просто хотите быстрое и удобочитаемое решение, это путь.
Вот мой ответ:
static struct rand_buffer {
unsigned v, count;
} buf2, buf3;
void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
buf->v = buf->v * n + v;
++buf->count;
}
#define PUSH(n, v) push (&buf##n, n, v)
int rand16 (void)
{
int v = buf2.v & 0xf;
buf2.v >>= 4;
buf2.count -= 4;
return v;
}
int rand9 (void)
{
int v = buf3.v % 9;
buf3.v /= 9;
buf3.count -= 2;
return v;
}
int rand7 (void)
{
if (buf3.count >= 2) {
int v = rand9 ();
if (v < 7)
return v % 7 + 1;
PUSH (2, v - 7);
}
for (;;) {
if (buf2.count >= 4) {
int v = rand16 ();
if (v < 14) {
PUSH (2, v / 7);
return v % 7 + 1;
}
PUSH (2, v - 14);
}
// Get a number between 0 & 25
int v = 5 * (rand5 () - 1) + rand5 () - 1;
if (v < 21) {
PUSH (3, v / 7);
return v % 7 + 1;
}
v -= 21;
PUSH (2, v & 1);
PUSH (2, v >> 1);
}
}
Это немного сложнее, чем другие, но я считаю, что это минимизирует количество вызовов rand5. Как и в случае с другими решениями, существует небольшая вероятность того, что он может зацикливаться в течение длительного времени.
Предполагая, что rand(n) здесь означает "случайное целое число в равномерном распределении от 0 до n-1", здесь приведен пример кода с использованием randint Python, который имеет такой эффект. Он использует только randint(5) и константы, чтобы произвести эффект randint (7). Немного глупо, на самом деле
from random import randint
sum = 7
while sum >= 7:
first = randint(0,5)
toadd = 9999
while toadd>1:
toadd = randint(0,5)
if toadd:
sum = first+5
else:
sum = first
assert 7>sum>=0
print sum
Предпосылка Адама Розенфилда заключается в следующем:
- x = 5 ^ n (в его случае: n= 2)
- манипулировать n вызовами rand5, чтобы получить число y в диапазоне [1, x]
- z = ((int) (x / 7)) * 7
- если y > z, попробуйте еще раз. еще вернуть y % 7 + 1
Когда n равно 2, у вас есть 4 возможности выбрасывания: y = {22, 23, 24, 25}. Если вы используете n равное 6, у вас есть только 1 выбрасывание: y = {15625}.
5 ^ 6 = 15625
7 * 2232 = 15624
Вы звоните rand5 больше раз. Однако у вас гораздо меньше шансов получить одноразовое значение (или бесконечный цикл). Если есть способ получить возможное выбрасываемое значение для y, я еще не нашел его.
Просто и эффективно:
int rand7 ( void )
{
return 4; // this number has been calculated using
// rand5() and is in the range 1..7
}
(Вдохновленный тем, какой ваш любимый мультфильм "программист"?).
Пока не осталось семи вариантов выбора, нарисуйте другое случайное число, которое умножает количество возможностей на пять. В Perl:
$num = 0;
$possibilities = 1;
sub rand7
{
while( $possibilities < 7 )
{
$num = $num * 5 + int(rand(5));
$possibilities *= 5;
}
my $result = $num % 7;
$num = int( $num / 7 );
$possibilities /= 7;
return $result;
}
Я не люблю диапазоны, начинающиеся с 1, поэтому я начну с 0:-)
unsigned rand5()
{
return rand() % 5;
}
unsigned rand7()
{
int r;
do
{
r = rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
} while (r > 15623);
return r / 2232;
}
Я знаю, что на него ответили, но, кажется, это работает нормально, но я не могу сказать вам, есть ли у него предвзятость. Мое "тестирование" предполагает, что это, по крайней мере, разумно.
Возможно, Адам Розенфилд будет достаточно любезен, чтобы прокомментировать?
Моя (наивная?) Идея такова:
Накапливайте rand5, пока не будет достаточно случайных битов, чтобы сделать rand7. Это займет не более 2 рандов. Для получения номера rand7 я использую накопленное значение mod 7.
Чтобы избежать переполнения аккумулятора, и поскольку аккумулятор является модом 7, тогда я беру мод 7 аккумулятора:
(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7
Функция rand7() выглядит следующим образом:
(Я позволил диапазону rand5 быть 0-4 и rand7 также 0-6.)
int rand7(){
static int a=0;
static int e=0;
int r;
a = a * 5 + rand5();
e = e + 5; // added 5/7ths of a rand7 number
if ( e<7 ){
a = a * 5 + rand5();
e = e + 5; // another 5/7ths
}
r = a % 7;
e = e - 7; // removed a rand7 number
a = a % 7;
return r;
}
Изменить: Добавлены результаты для 100 миллионов испытаний.
"Реальные" функции ранда 5 или 7
rand5: avg = 1.999802 0: 20003944 1: 19999889 2: 20003690 3: 19996938 4: 19995539 rand7: avg = 3.000111 0: 14282851 1: 14282879 2: 14284554 3: 14288546 4: 14292388 5: 14288736 6: 14280046
Мой ранд7
Среднее выглядит нормально, а распределение чисел тоже хорошо.
randt: avg=3.000080 0:14288793 1:14280135 2:14287848 3:14285277 4:14286341 5:14278663 6:14292943
Вот и все, равномерное распределение и ноль вызовов rand5.
def rand7:
seed += 1
if seed >= 7:
seed = 0
yield seed
Нужно заранее установить семена.
Есть элегантные алгоритмы, упомянутые выше, но вот один из способов приблизиться к этому, хотя это может быть обходным. Я предполагаю значения, сгенерированные из 0.
R2 = генератор случайных чисел, дающий значения меньше 2 (пробное пространство = {0, 1})
R8 = генератор случайных чисел, дающий значения меньше 8 (пробное пространство = {0, 1, 2, 3, 4, 5, 6, 7})
Чтобы сгенерировать R8 из R2, вы будете запускать R2 трижды и использовать объединенный результат всех 3 запусков как двоичное число с 3 цифрами. Вот диапазон значений, когда R2 запускается трижды:
0 0 0 -> 0
,
,
1 1 1 -> 7
Теперь, чтобы сгенерировать R7 из R8, мы просто запускаем R7 снова, если он возвращает 7:
int R7() {
do {
x = R8();
} while (x > 6)
return x;
}
Обходным решением является создание R2 из R5 (точно так же, как мы создали R7 из R8), затем R8 из R2 и затем R7 из R8.
Вот решение, которое полностью соответствует целым числам и находится в пределах примерно 4% от оптимального (то есть использует 1,26 случайных чисел в {0..4} для каждого из {0..6}). Код написан на Scala, но математика должна быть достаточно понятной на любом языке: вы используете тот факт, что 7^9 + 7^8 очень близок к 5^11. Таким образом, вы выбираете 11-значное число в базе 5, а затем интерпретируете его как 9-значное число в базе 7, если оно находится в диапазоне (задает 9-значное 7-значное число), или как 8-значное число, если оно превышает 9-значное число, и т. Д..:
abstract class RNG {
def apply(): Int
}
class Random5 extends RNG {
val rng = new scala.util.Random
var count = 0
def apply() = { count += 1 ; rng.nextInt(5) }
}
class FiveSevener(five: RNG) {
val sevens = new Array[Int](9)
var nsevens = 0
val to9 = 40353607;
val to8 = 5764801;
val to7 = 823543;
def loadSevens(value: Int, count: Int) {
nsevens = 0;
var remaining = value;
while (nsevens < count) {
sevens(nsevens) = remaining % 7
remaining /= 7
nsevens += 1
}
}
def loadSevens {
var fivepow11 = 0;
var i=0
while (i<11) { i+=1 ; fivepow11 = five() + fivepow11*5 }
if (fivepow11 < to9) { loadSevens(fivepow11 , 9) ; return }
fivepow11 -= to9
if (fivepow11 < to8) { loadSevens(fivepow11 , 8) ; return }
fivepow11 -= to8
if (fivepow11 < 3*to7) loadSevens(fivepow11 % to7 , 7)
else loadSevens
}
def apply() = {
if (nsevens==0) loadSevens
nsevens -= 1
sevens(nsevens)
}
}
Если вы вставите тест в интерпретатор (на самом деле REPL), вы получите:
scala> val five = new Random5
five: Random5 = Random5@e9c592
scala> val seven = new FiveSevener(five)
seven: FiveSevener = FiveSevener@143c423
scala> val counts = new Array[Int](7)
counts: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0)
scala> var i=0 ; while (i < 100000000) { counts( seven() ) += 1 ; i += 1 }
i: Int = 100000000
scala> counts
res0: Array[Int] = Array(14280662, 14293012, 14281286, 14284836, 14287188,
14289332, 14283684)
scala> five.count
res1: Int = 125902876
Распределение хорошее и плоское (в пределах примерно 10k от 1/7 от 10^8 в каждом бине, как и следовало ожидать из приблизительно гауссовского распределения).
Просто масштабируйте свой вывод из первой функции
0) you have a number in range 1-5
1) subtract 1 to make it in range 0-4
2) multiply by (7-1)/(5-1) to make it in range 0-6
3) add 1 to increment the range: Now your result is in between 1-7
Используя скользящий итог, вы можете оба
- поддерживать равное распределение; а также
- Не нужно жертвовать каким-либо элементом в случайной последовательности.
Обе эти проблемы являются проблемой с упрощенным rand(5)+rand(5)...решения. Следующий код Python показывает, как его реализовать (большая часть этого - доказательство распространения).
import random
x = []
for i in range (0,7):
x.append (0)
t = 0
tt = 0
for i in range (0,700000):
########################################
##### qq.py #####
r = int (random.random () * 5)
t = (t + r) % 7
########################################
##### qq_notsogood.py #####
#r = 20
#while r > 6:
#r = int (random.random () * 5)
#r = r + int (random.random () * 5)
#t = r
########################################
x[t] = x[t] + 1
tt = tt + 1
high = x[0]
low = x[0]
for i in range (0,7):
print "%d: %7d %.5f" % (i, x[i], 100.0 * x[i] / tt)
if x[i] < low:
low = x[i]
if x[i] > high:
high = x[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / tt)
И этот вывод показывает результаты:
pax$ python qq.py
0: 99908 14.27257
1: 100029 14.28986
2: 100327 14.33243
3: 100395 14.34214
4: 99104 14.15771
5: 99829 14.26129
6: 100408 14.34400
Variation = 1304 (0.18629%)
pax$ python qq.py
0: 99547 14.22100
1: 100229 14.31843
2: 100078 14.29686
3: 99451 14.20729
4: 100284 14.32629
5: 100038 14.29114
6: 100373 14.33900
Variation = 922 (0.13171%)
pax$ python qq.py
0: 100481 14.35443
1: 99188 14.16971
2: 100284 14.32629
3: 100222 14.31743
4: 99960 14.28000
5: 99426 14.20371
6: 100439 14.34843
Variation = 1293 (0.18471%)
Упрощенный rand(5)+rand(5), игнорируя те случаи, когда возвращается больше 6, типичное отклонение составляет 18%, что в 100 раз больше, чем у метода, показанного выше:
pax$ python qq_notsogood.py
0: 31756 4.53657
1: 63304 9.04343
2: 95507 13.64386
3: 127825 18.26071
4: 158851 22.69300
5: 127567 18.22386
6: 95190 13.59857
Variation = 127095 (18.15643%)
pax$ python qq_notsogood.py
0: 31792 4.54171
1: 63637 9.09100
2: 95641 13.66300
3: 127627 18.23243
4: 158751 22.67871
5: 126782 18.11171
6: 95770 13.68143
Variation = 126959 (18.13700%)
pax$ python qq_notsogood.py
0: 31955 4.56500
1: 63485 9.06929
2: 94849 13.54986
3: 127737 18.24814
4: 159687 22.81243
5: 127391 18.19871
6: 94896 13.55657
Variation = 127732 (18.24743%)
И, по совету Nixuz, я очистил скрипт, чтобы вы могли просто извлечь и использовать rand7... материал:
import random
# rand5() returns 0 through 4 inclusive.
def rand5():
return int (random.random () * 5)
# rand7() generator returns 0 through 6 inclusive (using rand5()).
def rand7():
rand7ret = 0
while True:
rand7ret = (rand7ret + rand5()) % 7
yield rand7ret
# Number of test runs.
count = 700000
# Work out distribution.
distrib = [0,0,0,0,0,0,0]
rgen =rand7()
for i in range (0,count):
r = rgen.next()
distrib[r] = distrib[r] + 1
# Print distributions and calculate variation.
high = distrib[0]
low = distrib[0]
for i in range (0,7):
print "%d: %7d %.5f" % (i, distrib[i], 100.0 * distrib[i] / count)
if distrib[i] < low:
low = distrib[i]
if distrib[i] > high:
high = distrib[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / count)
extern int r5();
int r7() {
return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}
Я думаю, что у меня есть четыре ответа, два из которых дают точные решения, подобные @Adam Rosenfield, но без проблемы с бесконечным циклом, и два других с почти идеальным решением, но более быстрой реализацией, чем первый.
Лучшее точное решение требует 7 звонков rand5, но давайте продолжим, чтобы понять.
Метод 1 - Точный
Сила ответа Адама в том, что он дает идеальное равномерное распределение, и существует очень высокая вероятность (21/25), что понадобятся только два вызова rand5(). Однако в худшем случае это бесконечный цикл.
Первое решение ниже также дает идеальное равномерное распределение, но требует в общей сложности 42 звонков rand5, Нет бесконечных петель.
Вот реализация R:
rand5 <- function() sample(1:5,1)
rand7 <- function() (sum(sapply(0:6, function(i) i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6)) %% 7) + 1
Для людей, не знакомых с R, вот упрощенная версия:
rand7 = function(){
r = 0
for(i in 0:6){
r = r + i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6
}
return r %% 7 + 1
}
Распределение rand5 будет сохранен Если мы посчитаем, каждая из 7 итераций цикла имеет 5^6 возможных комбинаций, таким образом, общее количество возможных комбинаций (7 * 5^6) %% 7 = 0, Таким образом, мы можем разделить случайные числа, сгенерированные на равные группы по 7. Для более подробного обсуждения см. Второй метод.
Вот все возможные комбинации:
table(apply(expand.grid(c(outer(1:5,0:6,"+")),(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
15625 15625 15625 15625 15625 15625 15625
Я думаю, что прямо сейчас показать, что метод Адама будет работать намного быстрее. Вероятность того, что есть 42 или более вызовов rand5 в решении Адама очень мало ((4/25)^21 ~ 10^(-17)).
Способ 2 - не точно
Теперь второй метод, который является почти равномерным, но требует 6 вызовов rand5:
rand7 <- function() (sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1
Вот упрощенная версия:
rand7 = function(){
r = 0
for(i in 1:6){
r = r + i*rand5()
}
return r %% 7 + 1
}
По сути, это одна итерация метода 1. Если мы сгенерируем все возможные комбинации, то получим подсчет:
table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
2233 2232 2232 2232 2232 2232 2232
Один номер появится еще раз в 5^6 = 15625 испытания.
Теперь, в методе 1, добавляя 1 к 6, мы перемещаем число 2233 в каждую последующую точку. Таким образом, общее количество комбинаций будет совпадать. Это работает, потому что 5^6 %% 7 = 1, а затем мы делаем 7 подходящих вариантов, поэтому (7 * 5^6 %% 7 = 0).
Метод 3 - Точный
Если аргумент метода 1 и 2 понятен, метод 3 следует и требует только 7 вызовов rand5, На данный момент, я чувствую, что это минимальное количество звонков, необходимое для точного решения.
Вот реализация R:
rand5 <- function() sample(1:5,1)
rand7 <- function() (sum(sapply(1:7, function(i) i * rand5())) %% 7) + 1
Для людей, не знакомых с R, вот упрощенная версия:
rand7 = function(){
r = 0
for(i in 1:7){
r = r + i * rand5()
}
return r %% 7 + 1
}
Распределение rand5 будет сохранен Если мы посчитаем, каждая из 7 итераций цикла имеет 5 возможных результатов, таким образом, общее количество возможных комбинаций (7 * 5) %% 7 = 0, Таким образом, мы можем разделить случайные числа, сгенерированные на равные группы по 7. Смотрите метод 1 и 2 для более подробного обсуждения этого вопроса.
Вот все возможные комбинации:
table(apply(expand.grid(0:6,(1:5)),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
5 5 5 5 5 5 5
Я думаю, прямо сейчас показать, что метод Адама все еще будет работать быстрее. Вероятность того, что есть 7 или более вызовов rand5 в решении Адама все еще мало ((4/25)^3 ~ 0.004).
Метод 4 - не точно
Это незначительная вариация второго метода. Это почти равномерно, но требует 7 звонков rand5это еще одно дополнение к методу 2:
rand7 <- function() (rand5() + sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1
Вот упрощенная версия:
rand7 = function(){
r = 0
for(i in 1:6){
r = r + i*rand5()
}
return (r+rand5()) %% 7 + 1
}
Если мы сгенерируем все возможные комбинации, вот результат подсчета:
table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6,1:5),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
11160 11161 11161 11161 11161 11161 11160
Два числа появятся один раз меньше в 5^7 = 78125 испытания. Для большинства целей я могу жить с этим.
В php
function rand1to7() {
do {
$output_value = 0;
for ($i = 0; $i < 28; $i++) {
$output_value += rand1to5();
}
while ($output_value != 140);
$output_value -= 12;
return floor($output_value / 16);
}
зацикливается, чтобы получить случайное число от 16 до 127, делится на шестнадцать, чтобы создать число от 1 до 7,9375, затем округляется, чтобы получить целое число от 1 до 7. Если я не ошибаюсь, есть шанс получить 16/112 любой из 7 результатов.
Этот ответ является скорее экспериментом по получению максимально возможной энтропии из функции Rand5. Поэтому он несколько неясен и почти наверняка намного медленнее, чем другие реализации.
Предполагая равномерное распределение от 0 до 4 и получающееся в результате равномерное распределение от 0 до 6:
public class SevenFromFive
{
public SevenFromFive()
{
// this outputs a uniform ditribution but for some reason including it
// screws up the output distribution
// open question Why?
this.fifth = new ProbabilityCondensor(5, b => {});
this.eigth = new ProbabilityCondensor(8, AddEntropy);
}
private static Random r = new Random();
private static uint Rand5()
{
return (uint)r.Next(0,5);
}
private class ProbabilityCondensor
{
private readonly int samples;
private int counter;
private int store;
private readonly Action<bool> output;
public ProbabilityCondensor(int chanceOfTrueReciprocal,
Action<bool> output)
{
this.output = output;
this.samples = chanceOfTrueReciprocal - 1;
}
public void Add(bool bit)
{
this.counter++;
if (bit)
this.store++;
if (counter == samples)
{
bool? e;
if (store == 0)
e = false;
else if (store == 1)
e = true;
else
e = null;// discard for now
counter = 0;
store = 0;
if (e.HasValue)
output(e.Value);
}
}
}
ulong buffer = 0;
const ulong Mask = 7UL;
int bitsAvail = 0;
private readonly ProbabilityCondensor fifth;
private readonly ProbabilityCondensor eigth;
private void AddEntropy(bool bit)
{
buffer <<= 1;
if (bit)
buffer |= 1;
bitsAvail++;
}
private void AddTwoBitsEntropy(uint u)
{
buffer <<= 2;
buffer |= (u & 3UL);
bitsAvail += 2;
}
public uint Rand7()
{
uint selection;
do
{
while (bitsAvail < 3)
{
var x = Rand5();
if (x < 4)
{
// put the two low order bits straight in
AddTwoBitsEntropy(x);
fifth.Add(false);
}
else
{
fifth.Add(true);
}
}
// read 3 bits
selection = (uint)((buffer & Mask));
bitsAvail -= 3;
buffer >>= 3;
if (selection == 7)
eigth.Add(true);
else
eigth.Add(false);
}
while (selection == 7);
return selection;
}
}
Количество битов, добавляемых в буфер за вызов к Rand5, в настоящее время составляет 4/5 * 2, то есть 1,6. Если включено значение вероятности 1/5, то оно увеличивается на 0,05, то есть на 1,65, но см. Комментарий в коде, где мне пришлось отключить это.
Биты, потребляемые при вызове Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 * (...
Это 3 + 3/8 + 3/64 + 3/512 ... примерно 3,42
Извлекая информацию из семерок, я восстанавливаю 1/8*1/7 бит на вызов, так что около 0,018
Это дает чистое потребление 3,4 бита на вызов, что означает, что соотношение составляет 2,125 вызовов к Rand5 для каждого Rand7. Оптимальным должно быть 2,1.
Я полагаю, что этот подход значительно медленнее, чем многие другие здесь, если только стоимость звонка в Rand5 не слишком высока (скажем, вызов какого-то внешнего источника энтропии).