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

Question

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

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

Answer 1

Почему это не сработает? Другой, кроме одного дополнительного вызова rand5 ()?

i = rand5() + rand5() + (rand5() - 1) //Random number between 1 and 14

i = i % 7 + 1;

Answer 2

Предполагая, что rand дает одинаковый вес всем битам, затем маскируется с верхней границей.

int i = rand(5) ^ (rand(5) & 2);

rand(5) можно вернуть только: 1b, 10b, 11b, 100b, 101b. Вам нужно только позаботиться о том, чтобы иногда устанавливать 2 бита.

Answer 3

Для значений 0-7 у вас есть следующее:

0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

По битам слева направо Rand5 () имеет p (1) = {2/5, 2/5, 3/5}. Поэтому, если мы дополним эти вероятностные распределения (~ Rand5 ()), мы сможем использовать это для получения нашего числа. Я постараюсь сообщить позже с решением. У кого-нибудь есть мысли?

R

Answer 4

Мы используем соглашение rand(n) -> [0, n - 1] здесь

Из многих ответов, которые я прочитал, они дают либо гарантию однородности, либо остановки, но не оба (второй ответ Адама Розенфельда).

Однако это возможно. У нас в основном это распределение:

Это оставляет нам дыру в распределении по [0-6]: 5 и 6 не имеют вероятность вхождения. Представьте себе, что теперь мы пытаемся заполнить это отверстие, распределение вероятностей и суммирование.

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

Поскольку каждый слот покрыт 5 из 7 сдвинутых распределений (сдвиг варьируется от От 0 до 6), и поскольку мы предполагаем, что случайные числа не зависят от одного ran5() позвони другому, получим

p(x) = 5 / 35 = 1 / 7       for all x in [0, 6]

Это означает, что, учитывая 7 независимых случайных чисел из ran5(), мы можем вычислить случайное число с равномерной вероятностью в диапазоне [0-6]. На самом деле, вероятность ran5 () распределение даже не должно быть равномерным, если образцы независимый (таким образом, распределение остается тем же самым от испытания до испытания). Кроме того, это действительно для других номеров, кроме 5 и 7.

Это дает нам следующую функцию python:

def rand_range_transform(rands):
    """
    returns a uniform random number in [0, len(rands) - 1]
    if all r in rands are independent random numbers from the same uniform distribution
    """
    return sum((x + i) for i, x in enumerate(rands)) % len(rands) # a single modulo outside the sum is enough in modulo arithmetic

Это можно использовать так:

rand5 = lambda : random.randrange(5)

def rand7():
    return rand_range_transform([rand5() for _ in range(7)])

Если мы позвоним rand7() 70000 раз, мы можем получить:

max: 6 min: 0 mean: 2.99711428571 std: 2.00194697049
0:  10019
1:  10016
2:  10071
3:  10044
4:  9775
5:  10042
6:  10033

Это хорошо, хотя далеко не идеально. Дело в том, что одно из наших предположений скорее всего ложь в этой реализации: мы используем PRNG, и, как таковой, результат следующего вызова зависит от последнего результата.

Тем не менее, используя действительно случайный источник чисел, вывод также должен быть действительно случайный И этот алгоритм заканчивается в каждом случае.

Но это обходится дорого: нам нужно 7 звонков на rand5() для одного rand7() звоните.

Answer 5

rand25() =5*(rand5()-1) + rand5()

rand7() { 
   while(true) {
       int r = rand25();
       if (r < 21) return r%3;         
   }
}

Почему это работает: вероятность того, что цикл будет работать вечно, равна 0.

Answer 6

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

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

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 испытаниях. В большинстве случаев я могу жить с этим.

Answer 7

function Rand7
   put 200 into x
   repeat while x > 118
      put ((random(5)-1) * 25) + ((random(5)-1) * 5) + (random(5)-1) into x
   end repeat
   return (x mod 7) + 1
end Rand7

Три вызова к Rand5, которые в среднем повторяются только 6 раз из 125.

Думайте об этом как о трехмерном массиве, 5x5x5, заполненном от 1 до 7 раз и 6 пробелами. Перекатывайтесь на заготовки. Вызовы rand5 создают трехзначный индекс base-5 в этом массиве.

Было бы меньше повторов с 4-мерными или более высокими N-мерными массивами, но это означает, что больше вызовов функции rand5 становятся стандартными. Вы начнете получать убывающую отдачу от эффективности при больших размерах. Три мне кажется хорошим компромиссом, но я не проверял их друг против друга, чтобы быть уверенным. И это будет зависеть от реализации rand5.

Answer 8

package CareerCup;

public class RangeTransform {
 static int counter = (int)(Math.random() * 5 + 1);

 private int func() {
  return (int) (Math.random() * 5 + 1);
 }

 private int getMultiplier() {
  return counter % 5 + 1;
 }

 public int rangeTransform() {
  counter++;
  int count = getMultiplier();
  int mult = func() + 5 * count;
  System.out.println("Mult is : " + 5 * count);
  return (mult) % 7 + 1;
 }

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  RangeTransform rangeTransform = new RangeTransform();
  for (int i = 0; i < 35; i++)
   System.out.println("Val is : " + rangeTransform.rangeTransform());
 }
}

Answer 9

Это самый простой ответ, который я мог создать после просмотра ответов других:

def r5tor7():
    while True:
        cand = (5 * r5()) + r5()
        if cand < 27:
            return cand

cand находится в диапазоне [6, 27], и возможные результаты равномерно распределены, если возможные результаты от r5 () распределены равномерно. Вы можете проверить мой ответ с этим кодом:

from collections import defaultdict

def r5_outcome(n):
    if not n:
        yield []
    else:
        for i in range(1, 6):
            for j in r5_outcome(n-1):
                yield [i] + j

def test_r7():
    d = defaultdict(int)
    for x in r5_outcome(2):
        s = sum([x[i] * 5**i for i in range(len(x))])
        if s < 27:
            d[s] += 1
    print len(d), d

r5_outcome(2) генерирует все возможные комбинации результатов r5 (). Я использую тот же фильтр для тестирования, что и в моем коде решения. Вы можете видеть, что все результаты одинаково, вероятно, потому что они имеют одинаковое значение.

Answer 10

int getOneToSeven(){
    int added = 0;
    for(int i = 1; i<=7; i++){
        added += getOneToFive();
    }
    return (added)%7+1;
}