Для функции, которая выдает случайное целое число в диапазоне от 1 до 5, напишите функцию, которая выдает случайное целое число в диапазоне от 1 до 7.

1. Что такое простое решение?
2. Каково эффективное решение для уменьшения использования памяти или работы на более медленном процессоре?

Это эквивалентно решению Адама Розенфилда, но может быть немного более понятным для некоторых читателей. Предполагается, что 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 ₂ Н. Таким образом, она rand5()имеет приблизительно 2,332193 бита энтропии и 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₁ a₂ a₃ ..., где каждая цифра a _iвыбирается вызовом rand5(). Например, если наш RNG выбрал a _i= 1 для всех i, тогда игнорируя тот факт, что это не очень случайно, это будет соответствовать действительному числу 1/5 + 1/5 ² + 1/5 ³ + ... = 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 заключается в следующем:

1. Умножить на 7
2. Неотъемлемой частью результата является следующая базовая 7 цифра
3. Вычтите неотъемлемую часть, оставив только дробную часть
4. Перейти к шагу 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
     }
}

Ниже приводится равномерное распределение в {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;
}    

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, и поэтому мы можем видеть, что этот метод может использоваться для перехода от любого генератора случайных чисел к любому другому генератору случайных чисел. Хотя небольшое смещение в сторону 0 всегда вводится при использовании показателя степени p-1.

Чтобы обобщить этот подход и быть более точным, мы можем иметь такую ​​функцию:

def getRandomconverted(frm, to):
    s = 0
    for i in range(to):
        s += getRandomUniform(frm)*frm**i
    mx = 0
    for i in range(to):
        mx = (to-1)*frm**i 
    mx = int(mx/to)*to # maximum value till which we can take mod
    if s < mx:
        return s%to
    else:
        return getRandomconverted(frm, to)

Здесь разрешены домашние задания?

Эта функция выполняет математику «базовый 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 в целые числа от 1to 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 в этом решении ниже по модулю, однако, если вы просто хотите быстрое и удобочитаемое решение, это путь.

Предполагая, что 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, я еще не нашел его.

Вот мой ответ:

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. Как и в случае с другими решениями, существует небольшая вероятность того, что он может зацикливаться в течение длительного времени.

Просто и эффективно:

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.

def rand7:
    seed += 1
    if seed >= 7:
        seed = 0
    yield seed

Нужно заранее установить семена.

Я знаю, что на него ответили, но, кажется, это работает нормально, но я не могу сказать вам, есть ли у него предвзятость. Мое «тестирование» предполагает, что это, по крайней мере, разумно.

Возможно, Адам Розенфилд будет достаточно любезен, чтобы прокомментировать?

Моя (наивная?) Идея такова:

Накапливайте 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

Есть элегантные алгоритмы, упомянутые выше, но вот один из способов приблизиться к этому, хотя это может быть обходным. Я предполагаю значения, сгенерированные из 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 в каждом бине, как и следовало ожидать из приблизительно гауссовского распределения).

Используя скользящий итог , вы можете оба

• поддерживать равное распределение; а также
• Не нужно жертвовать каким-либо элементом в случайной последовательности.

Обе эти проблемы являются проблемой с 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)

Этот ответ является скорее экспериментом по получению максимально возможной энтропии из функции 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 не слишком высока (скажем, вызов какого-то внешнего источника энтропии).

в 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 результатов.

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. Смотрите метод 2 для более подробного обсуждения этого.

Вот все возможные комбинации:

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 

Я думаю, прямо сейчас показать, что метод Адама будет работать намного быстрее. Вероятность того, что rand5в решении Адама есть 42 или более вызовов , очень мала ( (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. Смотрите метод один и два для более подробного обсуждения этого.

Вот все возможные комбинации:

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 

Я думаю, прямо сейчас показать, что метод Адама все еще будет работать быстрее. Вероятность того, что rand5в решении Адама будет 7 или более вызовов , все еще мала ( (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испытаниях. Для большинства целей я могу жить с этим.

Вам нужна функция rand1_7 () , я написал rand1_5 (), чтобы вы могли ее протестировать и построить.

import numpy
def rand1_5():
    return numpy.random.randint(5)+1

def rand1_7():
    q = 0
    for i in xrange(7):  q+= rand1_5()
    return q%7 + 1