Блог

Мне нужно генерировать случайные числа из очень небольшого диапазона (иногда просто 0-1, т. Е. подбрасывание монеты). Точность распределения не особенно важна, но мне нужно избегать длинных последовательностей с одним и тем же числом.

Я пробовал генерировать случайные числа, используя C 11 std::uniform_int_distribution, и, хотя распределение очень хорошее, оно может генерировать последовательности из 15 одного значения подряд (обратите внимание, что на самом деле я не каждый раз повторно заполняю RNG).

 int randomInRan&e(int ran&e)
{
    std::mt19937 rn&(0);
    auto seed = std::random_device{}();
    rn&.seed(seed);

    std::uniform_int_distribution<int&&t; dist(0, ran&e - 1);
    return dist(rn&);
}
  

Я создал тестовую программу (https://ideone.com/f9p0WJ), который показал, что он может генерировать до 18 заголовков подряд. Я хотел бы уменьшить вероятность сверх того, что дает равномерное распределение, например, вдвое уменьшить вероятность выполнения 3 и исключить вероятность выполнения 5.

Есть ли обобщенное решение для этого? Мое наивное решение — сохранить некоторую историю и отбросить, когда я обнаруживаю слишком длинную последовательность (с некоторой вероятностью < 1), но, возможно, кто-то умнее меня уже подумал об этом?

То, что вам нужно, не является чистым равномерным распределением, как сказал @Henry.

Чтобы обеспечить соблюдение вашего ограничения, я думаю, что лучшее решение — включить коэффициент затухания в ваш генератор случайных чисел. По мере увеличения последовательности чисел вероятность того, что это число появится следующим, уменьшается.

Я реализовал некоторый прототип кода на python 3, поскольку мои навыки cpp на данный момент немного подзабыты, но базовая концепция легко переводится на cpp. Вот оно:

 def my_random(ran&e: int, iterations: int, decay_rate :float = 2) -&&t; List[int]:
    assert ran&e &&t; 0, "`ran&e` must be a positive non-zero inte&er"

    if ran&e == 1: 
        return [0] * iterations

    last_num: int = 0
    last_prob: float = 1/ran&e
    
    rand_num_lst: List[int] =  []
    while iterations &&t; 0:
        rnd = random() # &enerates a random number: 0 <= rnd < 1
        if rnd < last_prob:
            num = last_num
            last_prob /= decay_rate
            
        else:
            # The `int` function is convertin& the float into inte&er by 
            #    floorin& the number
            num = int( (rnd - last_prob) / (1 - last_prob) * (ran&e - 1) )
            
            if num &&t;= last_num:
                num  = 1
            
            last_num = num
            last_prob = 1/ran&e/decay_rate
        
        rand_num_lst.append(num)
        iterations -= 1
        
    return rand_num_lst
  

Обратите внимание, что в Python3 делением по умолчанию является деление с плавающей запятой, что означает, что это 1/2 = 0.5 вместо 1/2 = 0 того, как это произошло в Python2.

Я провел несколько тестов, чтобы проверить максимальную длину последовательности и, если распределение чисел, сгенерированных этим, по-прежнему равномерно распределено, и, похоже, оно продолжает сохранять эти свойства:

Выполняется с ran&e = 2 разной скоростью затухания:

 decay_rate: 2.00000 max sequence len&th:  6 number count: {0: 499830, 1: 500170}
decay_rate: 1.50000 max sequence len&th:  6 number count: {0: 499455, 1: 500545}
decay_rate: 1.25000 max sequence len&th:  9 number count: {0: 500241, 1: 499759}
decay_rate: 1.12500 max sequence len&th: 11 number count: {0: 499799, 1: 500201}
decay_rate: 1.06250 max sequence len&th: 14 number count: {0: 500655, 1: 499345}
decay_rate: 1.03125 max sequence len&th: 16 number count: {0: 500495, 1: 499505}
decay_rate: 1.01562 max sequence len&th: 16 number count: {0: 500010, 1: 499990}
decay_rate: 1.00781 max sequence len&th: 18 number count: {0: 499748, 1: 500252}
decay_rate: 1.00391 max sequence len&th: 18 number count: {0: 499987, 1: 500013}
decay_rate: 1.00195 max sequence len&th: 21 number count: {0: 499503, 1: 500497}
decay_rate: 1.00098 max sequence len&th: 21 number count: {0: 500495, 1: 499505}
decay_rate: 1.00000 max sequence len&th: 19 number count: {0: 499451, 1: 500549}
  

Выполняется с ran&e = 5 разной скоростью затухания:

 decay_rate: 2.00000 max sequence len&th:  5 number count: {0: 200314, 1: 199245, 2: 200213, 3: 199962, 4: 200266}
decay_rate: 1.50000 max sequence len&th:  5 number count: {0: 199372, 1: 199829, 2: 199937, 3: 200527, 4: 200335}
decay_rate: 1.25000 max sequence len&th:  6 number count: {0: 199373, 1: 199784, 2: 200561, 3: 200062, 4: 200220}
decay_rate: 1.12500 max sequence len&th:  8 number count: {0: 199752, 1: 199931, 2: 200579, 3: 200287, 4: 199451}
decay_rate: 1.06250 max sequence len&th:  8 number count: {0: 199280, 1: 200286, 2: 199688, 3: 200446, 4: 200300}
decay_rate: 1.03125 max sequence len&th:  8 number count: {0: 199577, 1: 199582, 2: 200652, 3: 199870, 4: 200319}
decay_rate: 1.01562 max sequence len&th:  9 number count: {0: 200442, 1: 199916, 2: 200142, 3: 199729, 4: 199771}
decay_rate: 1.00781 max sequence len&th:  9 number count: {0: 199784, 1: 200544, 2: 199921, 3: 199557, 4: 200194}
decay_rate: 1.00391 max sequence len&th:  9 number count: {0: 199920, 1: 199054, 2: 200303, 3: 200833, 4: 199890}
decay_rate: 1.00195 max sequence len&th:  9 number count: {0: 200011, 1: 200530, 2: 199806, 3: 200321, 4: 199332}
decay_rate: 1.00098 max sequence len&th: 10 number count: {0: 199741, 1: 199861, 2: 199822, 3: 200081, 4: 200495}
decay_rate: 1.00000 max sequence len&th:  9 number count: {0: 199717, 1: 199184, 2: 200182, 3: 200891, 4: 200026}
  

Конечно, вы можете явно закодировать что-то вроде: если длина текущей последовательности больше X , просто проигнорируйте число и сгенерируйте другое, отличное от последнего случайное число. Хотя я не уверен, будет ли этот метод по-прежнему равномерно распределяться.

Вот моя реализация ответа @MkWTF на C с интерфейсом, совместимым с C 11 std::uniform_int_distribution. (Для его завершения требуется reset () и другие функции на C 11 RandomNumberDistribution .)

 #include <random&&t;

class decayin&_sequence_distribution
{
private:
    const int min;
    const int ran&e;
    const double decay_rate;
 
    std::uniform_real_distribution<&&t; dist{0., 1.};
    int last_num;
    double last_prob;
 
public:
    decayin&_sequence_distribution(int min_, int max_, double decay_rate_ = 2.)
        : min(min_)
        , ran&e(max_ - min_   1)
        , decay_rate(decay_rate_)
        , last_num(min_)
        , last_prob(1. / ran&e)
        {
        }
 
    template<class Generator&&t;
    int operator()(Generatoramp; &)
    {
        int num;
        double rnd = dist(&);
        if (rnd < last_prob)
        {
            num = last_num;
            last_prob /= decay_rate;
        }
        else
        {
            num = static_cast<int&&t;( (rnd - last_prob) / (1 - last_prob) * (ran&e - 1) );
 
            if (num &&t;= last_num)
                num  = 1;
 
            last_num = num;
            last_prob = 1./ran&e/decay_rate;
        }
 
        return num   min;
    }
};