0

我尝试编写一些代码来创建引导程序分发，虽然它可以编译，但我不确定它是否正常工作。一些背景知识：我教书的学校的一名学生系统地找到了我们计算机实验室笔记本电脑锁的密码，以与我们的计算机老师（幸运的是，不是我）搞砸。每个锁都有三个编号为 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)

调用 lock_hg(1000) 时的直方图 plt.hist(final_counts) 看起来相当均匀，40 或 50 次尝试与 900 或 950 一样常见。我认为它看起来更像以 500 为中心的正态分布。我不是确定代码是否有问题，或者我只是误解了数学。此代码是否适合该问题？如果没有，我该如何解决？如果它有效，是否有更有效的方法来做到这一点，如果是，它是什么？

4

3 回答 3

1

想象一下生成一个组合网格，每一行代表一个锁，每列值是该锁的可能组合。例如，假设有 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()

在此处输入图像描述

这种在网格中选择随机位置的方法清楚地表明分布应该是均匀的——正确的组合很可能出现在开始、结束或中间的任何位置。

于 2018-12-06T04:07:21.323 回答
0

是的，预计均匀分布。代码很好。

一种可能的优化是在删除之前将所选密钥与列表中的最后一个交换。这样可以避免接触中间的所有内容。

于 2018-12-06T03:24:59.713 回答
0

您可以进行两项改进：

  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
  1. 如果您尝试遍历所有可能的组合以进入某物（例如锁），最好增加一个而不是使用随机数生成器。我可能会误解这个问题，因为我不确定您是否想弄清楚他是如何做到的。
于 2018-12-06T03:32:46.433 回答