python - 在 Python 中使用组合数学列出 4 位密码

Question

我看到了这篇关于为什么使用 3 个唯一数字作为 4 位密码最安全的有趣文章:(LINK)

所涉及的数学非常简单 - 如果您必须根据屏幕上留下的污迹来猜测手机的 4 位数密码，那么:

4 个污点表示密码中有 4 个唯一数字。由于它们每个都必须至少使用一次，所以我们有 4! = 24 可能的密码。

有了 3 个不同的数字，密码变得更加安全。由于有 3 个污迹，因此重复了一个数字 - 但我们不知道是哪一个。因此考虑到多重性，我们得到 (4!/2!) x 3 = 36 可能的密码。

类似地，使用 2 个不同的数字，我们得到 14 个可能的密码。

我的问题是，有什么方法可以在 Python 中“证明”上述内容吗？一种证明 3 个数字给出最安全密码的方法，使用 Python 代码，如果你给它一些数字，可能会列出所有可能的密码？我正在考虑使用 itertools，以 itertools.permutations 作为起点，但后来我发现 Python 有一个组合模块，这可能是一种更优雅的方式。有人会好心地告诉我如何使用它吗？我现在正在阅读文档，但我忘记了一些语法。

Answer 1

标准发行版中没有combinatorics 模块，但这很容易做到。例如，

def guess(smudged_numbers):
    from itertools import product
    num_smudges = len(smudged_numbers)
    for raw in product(smudged_numbers, repeat=4):
        if len(set(raw)) == num_smudges:
            yield raw

count = 0
for nums in guess([1, 8]):
    print nums
    count += 1
print "total", count

打印:

(1, 1, 1, 8)
(1, 1, 8, 1)
(1, 1, 8, 8)
(1, 8, 1, 1)
(1, 8, 1, 8)
(1, 8, 8, 1)
(1, 8, 8, 8)
(8, 1, 1, 1)
(8, 1, 1, 8)
(8, 1, 8, 1)
(8, 1, 8, 8)
(8, 8, 1, 1)
(8, 8, 1, 8)
(8, 8, 8, 1)
total 14

搜索空间非常小(len(num_smudges)**4，最多 4**4 = 256)，所以没有必要做任何更奇特的事 ;-)

工作原理:它生成所有可能的 (product) 4 元组 (repeat=4)，其中包含传入的模糊数字序列。因此，对于 [1, 8]，它生成所有 2**4 = len(smudged_numbers)**4 = 16 个可能性的 4 元组只包含 1 和8 个。

将原始可能性转换为集合，然后告诉我们有多少(len)不同 数字出现在原始 4 元组中。我们只想要那些包含所有 污点数字的。这里的所有都是它的。在 [1, 8] 的情况下，此步骤仅剔除 16 个原始 4 元组中的 2 个:(1, 1, 1, 1) 和 (8, 8, 8, 8)。