Генерация случайных целых - PullRequest
Новая
       43

Генерация случайных целых

0 голосов
/ 29 апреля 2018

Я столкнулся с любопытным вопросом. Может быть, кто-нибудь может привести меня к соответствующей литературе.

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

import random

def count_no_repeat(i,j):
    random_set = set()
    while True:
        new_number = random.randint(i,j)
        if new_number in random_set:
            break
        random_set.add(new_number)
    return len(random_set) + 1

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

stats = []
for _ in range(1000):
    stats.append(count_no_repeat(1,n))

n - есть верхняя граница для целочисленного генератора.

И получил такие результаты: для n = 100: n equals 100

для n = 1000: n equals 1000

для n = 10000: n equals 10000

для n = 100000: n equals 100000

Итак, для этого эксперимента медиана:

  • растет относительно медленно;
  • остается на месте на графике (что также верно для эксперимента в 10 000 раз);

Кто может помочь и сказать, почему это так? Спасибо!

1 Ответ

0 голосов
/ 04 мая 2018

Вы вычисляете PDF обобщенной проблемы дня рождения. Это в основном все здесь, в https://en.wikipedia.org/wiki/Birthday_problem. Единственная проблема - страница вики говорит о CDF проблемы (см. Первый график здесь), вы выбираете PDF, значения p (n, k) - p (n, K-1). Вот ваш график выборки (синий) против PDF (оранжевый), если вам нужен код, просто скажите мне

enter image description here

UPDATE

В любом случае, лучше поместите код здесь, чтобы он не терялся. Все факториалы вычисляются как гамма-функции, а выражение для pbar / p выполняется через логарифмы, избегая переполнений, поэтому существуют вызовы логарифма функции Gamma, lgamma. 

import matplotlib.pyplot as plt
import numpy as np
import math
import random

def pbar(k, n): # as in wiki article, computed via log/exp
    l = 0
    try:
        l = math.lgamma(n + 1)  - math.lgamma(n - k + 1) - k*math.log(n)
    except ValueError:
        l = -50
    return math.exp(l)

def p(k, n):
    return 1.0 - pbar(k, n)

def count_no_repeat(i, j): # original sampling code
    random_set = set()
    while True:
        new_number = random.randint(i,j)
        if new_number in random_set:
            break
        random_set.add(new_number)
    return len(random_set) + 1

# 100 of numbers, 1mln of samples
n = 100
N = 1000000
stats = np.zeros(n+2, dtype = np.float32)
meds  = []

for _ in range(0, N):
    q = count_no_repeat(1, n)
    stats[q] += 1
    meds.append(q)

print(np.median(meds))

stats /= float(N)
x = np.linspace(0, n+1, n+2)

# computing PDF
z = []
for k in x:
    if k == 0:
        z.append(0)
    else:
        z.append(p(k, n) - p(k-1, n))

plt.plot(x, stats, 'o')
plt.plot(x, z)
plt.show()
...