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

Question

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

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

Answer 1

Ну вот, равномерное распределение и ноль вызовов rand5.

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

Необходимо заранее установить семена.

Answer 2

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

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

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

Накапливайте ранды 5, пока не будет достаточно случайных битов для создания ранда7. Это займет не более 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 миллионов испытаний.

'Real' rand functions mod 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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

extern int r5();

int r7() {
    return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}

Answer 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 не слишком высока (скажем, вызов некоторого внешнего источника энтропии).

Answer 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)

Answer 9

просто масштабируйте вывод из вашей первой функции

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

Answer 10

Вам нужна функция 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