Python - 生成 string.ascii_lowercase 的混乱

Question

我在网上找到了一些在 Python 中生成混乱的算法，但它们的复杂度都是指数级的，因此我无法让它们与一组 26 个元素（字母表）收敛！

所以我试图找到一种方法来改进以下代码（来源 此处）：

def derangement(vs):
    l = [None for x in vs]
    sol = set()
    sol.add(tuple(l))
    for v in vs:
        sol1 = set()
        for s in sol:
            for (i, v1) in enumerate(s):
                if not v1 and v != vs[i]:
                    s1 = list(s)
                    s1[i] = v
                    sol1.add(tuple(s1))
        sol = sol1
    return list(sol)

如果有人好奇，这是一个暴力替代密码求解器。我想看看暴力破解密码需要多长时间！

Answer 1

由于排列算法是 Ω(n!) ，没有什么能让你的代码收敛。这可能会更快，但这对于如此复杂的事情来说没有任何意义：

import itertools
def derangement(x):
    p = itertools.permutations(x)
    return (i for i in p if not any(i[k] == x[k] for k in range(len(x))))

它是一个惰性迭代器。如果您需要所有值（我怀疑您需要），只需 list() 即可

Answer 2

不一定，这取决于您使用的密码。如果您使用的是凯撒密码（我确定您不是），那么您只需尝试所有 26 个密码即可！排列，然后用真实的单词找到一个*（的），但我很确定你的意思是维吉尼亚密码，在这种情况下，你采取所有第一组排列，并将它们放在类似派系的行中，然后找到这些排列，然后交叉检查字典中的单词，然后你可能会得到一长串可能的消息，你必须对这些消息进行排序，找出有意义的消息。

Answer 3

只需要注意一下 26 个项目的混乱数量有多大：使用 SymPy 可以计算 26 个项目的混乱数量为 26 的次阶乘 (!26)

>>> subfactorial(26)
148362637348470135821287825
>>> round(log(_,2))
87

所以大约有 2^87 可能出现的字母顺序混乱。 此处有一些用于计算随机混乱的例程以及一种无需存储即可生成连续混乱的方法它们都按照上述初始问题中引用的例程存储在内存中。