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()了