Я скучаю по использованию генератора случайных чисел для начальной загрузки?

Question

Я попытался написать некоторый код для создания дистрибутива начальной загрузки и, хотя он компилируется, я не уверен, что он работает правильно.Немного предыстории: ученик в школе, где я преподаю, систематически находил комбинацию с замками на ноутбуках в нашей компьютерной лаборатории, чтобы прикрутить к нашему учителю компьютера (который, к счастью, не я).Каждый замок имеет три записи с номерами 0-9.Я рассчитываю, что есть 10 ^ 3 возможных комбинаций на замок.Он вел подробные списки комбинаций, которые он уже пробовал для каждой блокировки, поэтому каждая последующая попытка отбирает одну комбинацию без замены.Я пытаюсь смоделировать это, чтобы получить представление о том, сколько попыток он предпринял, чтобы разблокировать все эти компьютеры (в лаборатории 12 компьютеров), найдя ожидаемое значение для количества раз, которое потребуется для разблокировки одного из них.Это звучит как гипергеометрическое распределение для меня.Код, который я написал:

import numpy as np

def lock_hg(N):

    final_counts = []
    for i in range(N):
        count = 1
        combs = list(np.arange(1,1001,1))
        guess = np.random.randint(1,1000)
        for k in range(1000):
            a = np.random.choice(combs, 1)
            if a == guess:
                final_counts.append(count)
                break
            else:
                count = count + 1
                combs.remove(a)

    return(final_counts)

Гистограмма plt.hist (final_counts), когда вызывается lock_hg (1000), выглядит довольно равномерно с 40 или 50 попытками, столь же распространенными, как 900 или 950. Я думал, что этобыло бы больше похоже на нормальное распределение с центром в 500. Я не уверен, если есть проблема с кодом или я просто неправильно понимаю математику.Этот код подходит для проблемы?Если нет, как я могу это исправить?Если это работает, есть ли более эффективный способ сделать это, и если да, то что это?

Answer 1

Два улучшения, которые вы можете сделать:

1. Python имеет встроенный генератор случайных чисел.https://docs.python.org/2/library/random.html

import random

for i in range(5):
    print(random.randint(0, 100))

10
38
53
83
23

Если вы пытаетесь перебрать все возможные комбинации, чтобы попасть во что-то (например, в замок), лучше использовать одну из них вместо использования генератора случайных чисел.Я мог бы неправильно понять вопрос, так как не уверен, пытаетесь ли вы выяснить, как он это сделал.

Answer 2

Представьте себе создание сетки комбинаций, где каждая строка представляет блокировку, а значение каждого столбца - возможную комбинацию для этой блокировки.Например, предположим, что есть 10 блокировок и только 5 возможных комбинаций на блокировку.Вы можете генерировать их все в случайном порядке, например:

In [42]: np.random.seed(2018) # to make the example reproducible
In [43]: grid = np.random.random((10,5)).argsort(axis=1); grid
Out[43]: 
array([[1, 3, 4, 0, 2],
       [4, 0, 2, 3, 1],
       [3, 4, 2, 0, 1],
       [2, 1, 3, 4, 0],
       [1, 3, 0, 4, 2],
       [1, 0, 4, 3, 2],
       [2, 0, 1, 3, 4],
       [2, 0, 3, 4, 1],
       [2, 3, 1, 0, 4],
       [2, 4, 0, 3, 1]])

Далее, давайте выберем случайную комбинацию для каждого из 10 замков:

In [48]: combo = np.random.choice(5, size=10, replace=True); combo
Out[48]: array([3, 2, 3, 3, 4, 4, 4, 3, 2, 3])

Мы можем думатьgrid как указание порядка, в котором используются комбинации для каждой блокировки.И мы можем взять combo в качестве фактической комбинации для каждого замка.

Мы также можем визуализировать расположение матчей, используя:

plt.imshow((grid == combo[:, None])[::-1], origin='upper')

и мы можем найти местоположение каждого успешного совпадения в нашей сетке, используя argmax:

In [73]: (grid == combo[:, None]).argmax(axis=1)
Out[73]: array([1, 2, 0, 2, 3, 2, 4, 2, 0, 3])

argmax возвращает индекс (местоположение) совпадениядля каждого ряда.Эти индексы также указывают количество попыток, необходимых для поиска каждого совпадения.Ну, почти.Поскольку Python основан на 0 индексах, argmax вернет 0, если совпадение произойдет с первой попытки.Поэтому нам нужно добавить 1 к (grid == combo[:, None]).argmax(axis=1), чтобы получить истинное количество попыток.

Итак, мы ищем распределение (grid == combo[:, None]).argmax(axis=1) + 1.Теперь, когда мы разработали вычисления для 10 блокировок и 5 комбинаций, легко увеличить это, скажем, до 10000 блокировок и 1000 комбинаций:

import numpy as np
import matplotlib.pyplot as plt
np.random.seed(2018)

num_locks = 10000
num_combos = 1000

grid = np.random.random((num_locks, num_combos)).argsort(axis=1)
combo = np.random.choice(num_combos, size=num_locks, replace=True)
attempts = (grid == combo[:, None]).argmax(axis=1) + 1

plt.hist(attempts, density=True)
plt.show()

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

Answer 3

Ожидается равномерное распределение, да.Код в порядке.

Возможная оптимизация состояла бы в том, чтобы поменять выбранный ключ с последним в списке перед его удалением.Это позволит избежать касания всех тех, кто находится между ними.