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

решение в php

<?php
function random_5(){
    return rand(1,5);
}


function random_7(){
 $total = 0;

    for($i=0;$i<7;$i++){
        $total += random_5();
    }

    return ($total%7)+1; 
}

echo random_7();
?>

Проблемы домашней работы позволяются здесь?

Эта функция делает сырую нефть, "основывают 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;
}

int ans = 0;
while (ans == 0) 
{
     for (int i=0; i<3; i++) 
     {
          while ((r = rand5()) == 3){};
          ans += (r < 3) >> i
     }
}

rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1

Редактирование: Это не вполне работает. Это выключено приблизительно 2 частями в 1 000 (принятие идеальных 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

Путем переключения на сумму [1 110]

n   Error%
10  +/- 1e-3,
12  +/- 1e-4,
14  +/- 1e-5,
16  +/- 1e-6,
...
28  +/- 3e-11

, кажется, получает порядок величины для каждых 2, добавил

BTW: таблица ошибок выше не была сгенерирована через выборку, но следующим рекуррентным соотношением:

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 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 );
    }
}

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

Следующее производит равномерное распределение на {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;
}    

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

(Я украл ответ Адама Розенфельда и заставил его работать примерно на 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()

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

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

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

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

This is equivalent to Adam Rosenfield's solution, but may be a bit more clear for some readers. It assumes rand5() is a function that returns a statistically random integer in the range 1 through 5 inclusive.

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;
}

How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it's a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That's what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don't get a good result, we keep throwing darts.

Like Adam said, this can run forever in the worst case, but statistically the worst case never happens. :)

Этот ответ больше представляет собой эксперимент по получению максимально возможной энтропии от функции Rand5. Поэтому t несколько неясен и почти наверняка намного медленнее, чем другие реализации.

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

Если мы рассмотрим дополнительное ограничение попытки дать наиболее эффективный ответ, т.е. один, которому задан входной поток I , равномерно распределенных целых чисел длиной м от 1 до 5, выводит поток O равномерно распределенных целых чисел от 1 до 7 наибольшей длины относительно м , скажем L (м) .

Самый простой способ проанализировать это - рассматривать потоки I и O как 5-арные и 7-арные числа соответственно. Это достигается с помощью идеи основного ответа о взятии потока a1, a2, a3, ... -> a1 + 5 * a2 + 5 ^ 2 * a3 + .. и аналогично для потока O .

Затем, если мы возьмем часть входного потока длиной m, выберите n s. т. 5 ^ m-7 ^ n = c , где c> 0 и как можно меньше. Затем есть единообразное отображение входного потока длины m в целые числа от 1 до 5 ^ m и еще одно равномерное отображение из целых чисел от 1 до 7 ^ n ] в выходной поток длины n, где нам, возможно, придется потерять несколько случаев из входного потока, когда отображаемое целое число превышает 7 ^ n .

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

Тогда все будет основано на распределении семизначных цифр 5 ^ m для различные значения м .

Я уверен, что есть много теории, которая покрывает это, я могу взглянуть и сообщить в какой-то момент.

Все это тогда основывается на распределении семизначных цифр 5 мкм для различных значений м .

Я уверен, что их много теории, которая охватывает это, я могу взглянуть и доложить в какой-то момент.

Все это тогда основывается на распределении семизначных цифр 5 мкм для различных значений м .

Я уверен, что их много теории, которая охватывает это, я могу взглянуть и доложить в какой-то момент.

I'd like to add another answer, in addition to my first answer. This answer attempts to minimize the number of calls to rand5() per call to rand7(), to maximize the usage of randomness. That is, if you consider randomness to be a precious resource, we want to use as much of it as possible, without throwing away any random bits. This answer also has some similarities with the logic presented in Ivan's answer.

The entropy of a random variable is a well-defined quantity. For a random variable which takes on N states with equal probabilities (a uniform distribution), the entropy is log₂ N. Thus, rand5() has approximately 2.32193 bits of entropy, and rand7() has about 2.80735 bits of entropy. If we hope to maximize our use of randomness, we need to use all 2.32193 bits of entropy from each call to rand5(), and apply them to generating 2.80735 bits of entropy needed for each call to rand7(). The fundamental limit, then, is that we can do no better than log(7)/log(5) = 1.20906 calls to rand5() per call to rand7().

Side notes: all logarithms in this answer will be base 2 unless specified otherwise. rand5() will be assumed to return numbers in the range [0, 4], and rand7() will be assumed to return numbers in the range [0, 6]. Adjusting the ranges to [1, 5] and [1, 7] respectively is trivial.

So how do we do it? We generate an infinitely precise random real number between 0 and 1 (pretend for the moment that we could actually compute and store such an infinitely precise number -- we'll fix this later). We can generate such a number by generating its digits in base 5: we pick the random number 0.a₁a₂a₃..., where each digit a_i is chosen by a call to rand5(). For example, if our RNG chose a_i = 1 for all i, then ignoring the fact that that isn't very random, that would correspond to the real number 1/5 + 1/5² + 1/5³ + ... = 1/4 (sum of a geometric series).

Ok, so we've picked a random real number between 0 and 1. I now claim that such a random number is uniformly distributed. Intuitively, this is easy to understand, since each digit was picked uniformly, and the number is infinitely precise. However, a formal proof of this is somewhat more involved, since now we're dealing with a continuous distribution instead of a discrete distribution, so we need to prove that the probability that our number lies in an interval [a, b] equals the length of that interval, b - a. The proof is left as an exercise for the reader =).

Now that we have a random real number selected uniformly from the range [0, 1], we need to convert it to a series of uniformly random numbers in the range [0, 6] to generate the output of rand7(). How do we do this? Just the reverse of what we just did -- we convert it to an infinitely precise decimal in base 7, and then each base 7 digit will correspond to one output of rand7().

Taking the example from earlier, if our rand5() produces an infinite stream of 1's, then our random real number will be 1/4. Converting 1/4 to base 7, we get the infinite decimal 0.15151515..., so we will produce as output 1, 5, 1, 5, 1, 5, etc.

Ok, so we have the main idea, but we have two problems left: we can't actually compute or store an infinitely precise real number, so how do we deal with only a finite portion of it? Secondly, how do we actually convert it to base 7?

One way we can convert a number between 0 and 1 to base 7 is as follows:

1. Multiply by 7
2. The integral part of the result is the next base 7 digit
3. Subtract off the integral part, leaving only the fractional part
4. Goto step 1

To deal with the problem of infinite precision, we compute a partial result, and we also store an upper bound on what the result could be. That is, suppose we've called rand5() twice and it returned 1 both times. The number we've generated so far is 0.11 (base 5). Whatever the rest of the infinite series of calls to rand5() produce, the random real number we're generating will never be larger than 0.12: it is always true that 0.11 ≤ 0.11xyz... < 0.12.

So, keeping track of the current number so far, and the maximum value it could ever take, we convert both numbers to base 7. If they agree on the first k digits, then we can safely output the next k digits -- regardless of what the infinite stream of base 5 digits are, they will never affect the next k digits of the base 7 representation!

And that's the algorithm -- to generate the next output of rand7(), we generate only as many digits of rand5() as we need to ensure that we know with certainty the value of the next digit in the conversion of the random real number to base 7. Here is a Python implementation, with a test harness:

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)

Note that rand7_gen() returns a generator, since it has internal state involving the conversion of the number to base 7. The test harness calls next(r7) 10000 times to produce 10000 random numbers, and then it measures their distribution. Only integer math is used, so the results are exactly correct.

Also note that the numbers here get very big, very fast. Powers of 5 and 7 grow quickly. Hence, performance will start to degrade noticeably after generating lots of random numbers, due to bignum arithmetic. But remember here, my goal was to maximize the usage of random bits, not to maximize performance (although that is a secondary goal).

In one run of this, I made 12091 calls to rand5() for 10000 calls to rand7(), achieving the minimum of log(7)/log(5) calls on average to 4 significant figures, and the resulting output was uniform.

In order to port this code to a language that doesn't have arbitrarily large integers built-in, you'll have to cap the values of pow5 and pow7 to the maximum value of your native integral type -- if they get too big, then reset everything and start over. This will increase the average number of calls to rand5() per call to rand7() very slightly, but hopefully it shouldn't increase too much even for 32- or 64-bit integers.

Предпосылка, лежащая в основе правильного ответа Адама Розенфилда:

• x = 5 ^ n (в его случае: n = 2)
• манипулировать n rand5 вызывает число y в диапазоне [1, x]
• z = ((int) (x / 7)) * 7
• если y> z, попробуйте еще раз . else return 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. Как и в случае с другими решениями, существует небольшая вероятность того, что это может зацикливаться в течение длительного времени.

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

Почему бы не сделать это просто?

int random7() {
  return random5() + (random5() % 3);
}

Шансы получить 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;
}

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

Вот так, равномерное распределение и нулевой вызов rand5.

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

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

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

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

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

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

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

"Настоящие" функции rand, мод 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

Мой rand7

Среднее значение выглядит нормально, и распределения чисел тоже выглядят нормально.

randt: avg = 3.000080 0: 14288793 1: 14280135 2: 14287848 3: 14285277 4: 14286341 5: 14278663 6: 14292943

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

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

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

int rand7 ( void )
{
    return 4; // this number has been calculated using
              // rand5() and is in the range 1..7
}

(На основе Какой ваш любимый мульт про "программист"? ).

Вот решение, которое пытается минимизировать количество вызовов к 5 рэндам () при сохранении реализации простой и эффективной; в частности, это не требует произвольных больших целых чисел в отличие от Adam Rosenfield’s второй ответ. Это использует то, что 23/19 = 1.21052... является хорошим рациональным приближением для входа (7) журнал / (5) = 1.20906..., таким образом мы можем генерировать 19 случайных элементов {1..., 7} из 23 случайных элементов {1..., 5} выборкой отклонения только с маленькой вероятностью отклонения. В среднем, алгоритм ниже взятий приблизительно 1,266 вызова к 5 рэндам () для каждого вызова к 7 рэндам (). Если распределение 5 рэндов () равномерно, так 7 рэндов ().

uint_fast64_t pool;

int capacity = 0;

void new_batch (void)
{
  uint_fast64_t r;
  int i;

  do {
    r = 0;
    for (i = 0; i < 23; i++)
      r = 5 * r + (rand5() - 1);
  } while (r >= 11398895185373143ULL);  /* 7**19, a bit less than 5**23 */

  pool = r;
  capacity = 19;
}

int rand7 (void)
{
  int r;

  if (capacity == 0)
    new_batch();

  r = pool % 7;
  pool /= 7;
  capacity--;

  return r + 1;
}

#!/usr/bin/env ruby
class Integer
  def rand7
    rand(6)+1
  end
end

def rand5
  rand(4)+1
end

x = rand5() # x => int between 1 and 5

y = x.rand7() # y => int between 1 and 7

.. хотя это может считаться мошенничеством ..

int rand7()
{
    int zero_one_or_two = ( rand5() + rand5() - 1 ) % 3 ;
    return rand5() + zero_one_or_two ;
}

Я чувствую себя глупо перед всеми этими сложными ответами.

Почему это не может быть:

int random1_to_7()
{
  return (random1_to_5() * 7) / 5;  
}

?