Расширить случайный диапазон от 1–5 до 1–7

Question

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

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

Answer 1

Это решение не тратит энтропию и дает первое доступное по-настоящему случайное число в диапазоне. С каждой итерацией вероятность не получить ответ доказуемо уменьшается. Вероятность получения ответа в N итераций - это вероятность того, что случайное число от 0 до max (5 ^ N) будет меньше, чем наибольшее число из семи в этом диапазоне (max-max% 7). Должен повторяться как минимум дважды. Но это обязательно верно для всех решений.

int random7() {
  range = 1;
  remainder = 0;

  while (1) {
    remainder = remainder * 5 + random5() - 1;
    range = range * 5;

    limit = range - (range % 7);
    if (remainder < limit) return (remainder % 7) + 1;

    remainder = remainder % 7;
    range = range % 7;
  }
}

Численно эквивалентно:

r5=5;
num=random5()-1;
while (1) {
   num=num*5+random5()-1;
   r5=r5*5;
   r7=r5-r5%7;
   if (num<r7) return num%7+1;
}

Первый код вычисляет его по модулю. Второй код просто математика. Или я где-то ошибся. : -)

Answer 2

Вот что я нашел:

1. Random5 создает диапазон от 1 до 5, случайным образом распределенный
2. Если мы запустим его 3 раза и сложим вместе, мы получим диапазон 3 ~ 15, случайным образом распределенный
3. Выполнить арифметику в диапазоне 3 ~ 15
   1. (3 ~ 15) - 1 = (2 ~ 14)
   2. (2 ~ 14) / 2 = (1 ~ 7)

Затем мы получаем диапазон от 1 до 7, то есть Random7, который мы ищем.

Answer 3

Я подумал об интересном решении этой проблемы и хотел поделиться им.

function rand7() {

    var returnVal = 4;

    for (var n=0; n<3; n++) {
        var rand = rand5();

        if (rand==1||rand==2){
            returnVal+=1;
        }
        else if (rand==3||rand==4) {
            returnVal-=1;
        }
    }

    return returnVal;
}

Я создал тестовую функцию, которая перебирает rand7 () 10000 раз, суммирует все возвращаемые значения и делит ее на 10000. Если rand7 () работает правильно, наше вычисленное среднее значение должно быть 4 - например, (1 + 2 + 3 + 4 + 5 + 6 + 7/7) = 4. После выполнения нескольких тестов среднее значение действительно верно при 4 :)

Answer 4

как насчет этого

* * Rand5 тысяча два ()% 2 + rand5 ()% 2 + rand5 ()% 2 + rand5 ()% 2 + rand5 ()% 2 + rand5 ()% 2

Не уверен, что это равномерно распределено. Есть предложения?

Answer 5

Здесь есть много решений, которые не дают равномерного распределения, и многие комментарии указывают на это, но вопрос не устанавливает это как требование . Самое простое решение:

int rand_7() { return rand_5(); }

Случайное целое число в диапазоне 1 - 5 явно находится в диапазоне 1 - 7. Ну, технически самое простое решение - вернуть константу, но это слишком тривиально.

Однако я думаю, что существование функции rand_5 - это красная сельдь. Предположим, что вопрос был задан как «создать равномерно распределенный генератор псевдослучайных чисел с целочисленным выводом в диапазоне 1 - 7». Это простая проблема (не технически простая, но уже решенная, так что вы можете ее найти.)

С другой стороны, если вопрос интерпретируется как означающий, что у вас действительно есть генератор действительно случайных чисел для целых чисел в диапазоне 1 - 5 (не псевдослучайный), то решение будет таким:

1) examine the rand_5 function
2) understand how it works
3) profit

Answer 6

1. Что такое простое решение? (rand5() + rand5()) % 7 + 1
   
2. Каково эффективное решение для уменьшения использования памяти или работы на более медленном процессоре? Yes, this is effective as it calls rand5() only twice and have O(1) space complexity
   

Рассмотрим rand5() выдает случайные числа от 1 до 5 (включительно).
(1 + 1)% 7 + 1 = 3
(1 + 2)% 7 + 1 = 4
(1 + 3)% 7 + 1 = 5
(1 + 4)% 7 + 1 = 6
(1 + 5)% 7 + 1 = 7

(2 + 1)% 7 + 1 = 4
(2 + 2)% 7 + 1 = 5
(2 + 3)% 7 + 1 = 6
(2 + 4)% 7 + 1 = 7
(2 + 5)% 7 + 1 = 1
...

(5 + 1)% 7 + 1 = 7
(5 + 2)% 7 + 1 = 1
(5 + 3)% 7 + 1 = 2
(5 + 4)% 7 + 1 = 3
(5 + 5)% 7 + 1 = 4
...

и т. Д.

Answer 7

Вот моя общая реализация генерации униформы в диапазоне [0, N-1] с учетом генератора униформы в диапазоне [0, B-1].

public class RandomUnif {

    public static final int BASE_NUMBER = 5;

    private static Random rand = new Random();

    /** given generator, returns uniform integer in the range 0.. BASE_NUMBER-1
    public static int randomBASE() {
        return rand.nextInt(BASE_NUMBER);
    }

    /** returns uniform integer in the range 0..n-1 using randomBASE() */
    public static int randomUnif(int n) {
        int rand, factor;
        if( n <= 1 ) return 0;
        else if( n == BASE_NUMBER ) return randomBASE();
        if( n < BASE_NUMBER ) {
            factor = BASE_NUMBER / n;
            do
                rand = randomBASE() / factor;
            while(rand >= n);
            return rand;
        } else {
            factor = (n - 1) / BASE_NUMBER + 1;
            do {
                rand = factor * randomBASE() + randomUnif(factor);
            } while(rand >= n);
            return rand;
        }
    }
}

Не эффектно эффективный, но общий и компактный. Имеются в виду звонки на базу генератора:

 n  calls
 2  1.250 
 3  1.644 
 4  1.252 
 5  1.000 
 6  3.763 
 7  3.185 
 8  2.821 
 9  2.495 
10  2.250 
11  3.646 
12  3.316 
13  3.060 
14  2.853 
15  2.650 
16  2.814 
17  2.644 
18  2.502 
19  2.361 
20  2.248 
21  2.382 
22  2.277 
23  2.175 
24  2.082 
25  2.000 
26  5.472 
27  5.280 
28  5.119 
29  4.899 

Answer 8

int rand7()
{
    return ( rand5() + (rand5()%3) );
}

1. rand5 () - возвращает значения от 1-5
2. rand5 ()% 3 - возвращает значения от 0-2
3. Итак, при суммировании общее значение будет между 1-7

Answer 9

Вот ответ с использованием возможностей C ++ 11

#include <functional>
#include <iostream>
#include <ostream>
#include <random>

int main()
{
    std::random_device rd;
    unsigned long seed = rd();
    std::cout << "seed = " << seed << std::endl;

    std::mt19937 engine(seed);

    std::uniform_int_distribution<> dist(1, 5);
    auto rand5 = std::bind(dist, engine);

    const int n = 20;
    for (int i = 0; i != n; ++i)
    {
        std::cout << rand5() << " ";
    }
    std::cout << std::endl;

    // Use a lambda expression to define rand7
    auto rand7 = [&rand5]()->int
    {
        for (int result = 0; ; result = 0)
        {
            // Take advantage of the fact that
            // 5**6 = 15625 = 15624 + 1 = 7 * (2232) + 1.
            // So we only have to discard one out of every 15625 numbers generated.

            // Generate a 6-digit number in base 5
            for (int i = 0; i != 6; ++i)
            {
                result = 5 * result + (rand5() - 1);
            }

            // result is in the range [0, 15625)
            if (result == 15625 - 1)
            {
                // Discard this number
                continue;
            }

            // We now know that result is in the range [0, 15624), a range that can
            // be divided evenly into 7 buckets guaranteeing uniformity
            result /= 2232;
            return 1 + result;
        }
    };

    for (int i = 0; i != n; ++i)
    {
        std::cout << rand7() << " ";
    }
    std::cout << std::endl;

    return 0;
}

Answer 10

function rand7() {
    while (true) { //lowest base 5 random number > 7 reduces memory
        int num = (rand5()-1)*5 + rand5()-1;
    if (num < 21)  // improves performance
        return 1 + num%7;
    }
}

Код Python:

from random import randint
def rand7():
    while(True):
        num = (randint(1, 5)-1)*5 + randint(1, 5)-1
        if num < 21:
                return 1 + num%7

Тестовый дистрибутив для 100000 прогонов:

>>> rnums = []
>>> for _ in range(100000):
    rnums.append(rand7())
>>> {n:rnums.count(n) for n in set(rnums)}
{1: 15648, 2: 15741, 3: 15681, 4: 15847, 5: 15642, 6: 15806, 7: 15635}