Я не использую генератор случайных чисел numpy для начальной загрузки?
Я попытался написать код для создания дистрибутива начальной загрузки, и, хотя он компилируется, я не уверен, что он работает правильно. Немного предыстории: ученик школы, где я преподаю, систематически находил комбинацию замков на ноутбуках в нашей компьютерной лаборатории, чтобы порвать с нашим учителем по информатике (который, к счастью, не я). Каждый замок имеет три записи с номерами от 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. Я не конечно, если есть проблема с кодом, или я просто неправильно понимаю математику. Подходит ли этот код для решения проблемы? Если нет, то как это исправить? Если он работает, есть ли более эффективный способ сделать это, и если да, то какой?
Ответы 3
Да, ожидается равномерное распределение. Код в порядке.
Возможной оптимизацией будет замена выбранного ключа последним в списке перед его удалением. Это позволит избежать прикосновения ко всем промежуточным.
Вы можете сделать два улучшения:
- 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
- Если вы пытаетесь перебрать все возможные комбинации, чтобы получить что-то (например, блокировку), лучше подняться на одну, а не использовать генератор случайных чисел. Я могу немного неправильно понять вопрос, поскольку я не уверен, пытаетесь ли вы выяснить, как он это сделал.
Да, ты можешь это сделать. Однако использование случайных чисел быстро раздражает, поскольку вам, вероятно, придется проверить, не используются ли повторяющиеся числа. Кроме того, в среднем это будет 500 попыток, поскольку генератор случайный, он мог сделать от 1 попытки до 999 попыток, причем все числа от среднего до примерно 500.
Представьте, что вы генерируете сетку комбинаций, каждая строка которой представляет замок и каждое значение столбца представляет собой возможную комбинацию для этой блокировки. Например, предположим, что есть 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()
Этот метод выбора случайного места в сетке дает понять, что распределение должно быть равномерным - так же вероятно, что произойдет правильная комбинация в начале, как в конце, или в любом месте между ними.
Я согласен, что лучше подниматься по одному. Похоже, этот ребенок какое-то время делал это (пробовал 1,1,1, затем 1,1,2, затем 1,1,3 ... и т. д.), А потом ему было скучно и он пробовал что-то совершенно случайное. Если бы это было не так, я бы мог пропустить весь второй цикл и просто сгенерировать случайное число от 1 до 1000, и это число будет соответствовать комбинации (0,0,0 может соответствовать 1; 0,1 , 0 соответствует 11 и т. д.). Если бы он сделал это таким образом, я мог бы узнать комбинацию каждого замка и точно подсчитать, сколько попыток он сделал.