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

这里有个小提示，关于26个物品的错位排列有多庞大：用SymPy这个工具，我们可以计算出26个物品的错位排列数量，也就是26的子阶乘（!26）。

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

所以，字母表的错位排列大约有2^87种可能性。这里有一些程序可以用来计算随机的错位排列，另外还有一种方法可以生成连续的错位排列，而不需要把所有的排列都存储在内存中，就像上面提到的初始问题中的程序那样。

Answer 2

这不一定，具体要看你用的是什么加密方式。如果你用的是凯撒密码，我相信你不是，那你只需要尝试所有26种排列，然后找出其中有真实单词的那种。不过我觉得你说的是维吉尼亚密码。在这种情况下，你需要先生成一组排列，然后把这些排列排成类似的行，再找出这些排列，接着对照字典检查单词。这样你可能会得到一长串可能的消息，然后你得从中筛选出一个有意义的。

Answer 3

因为排列算法的复杂度是Ω(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()把它转换成列表就可以了。