1

我在网上找到了一些算法来在 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)

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

4

3 回答 3

5

由于置换算法是 Ω(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()它

于 2011-06-15T02:30:47.367 回答
1

不一定，这取决于您使用的密码。如果您使用的是凯撒密码，我确定您不是，您只需尝试所有 26 个！排列，然后用真实的单词找到一个 *('s) 但我很确定你的意思是 vigenere cypher 在这种情况下，你把所有的第一组排列放在一个类似派系的行中，然后找到这些排列，然后交叉检查字典单词，然后你可能会得到一个很长的可能消息列表，你必须对那些有意义的消息进行排序。

于 2012-02-02T21:33:16.643 回答
0

只需说明 26 项的紊乱数有多大：使用 SymPy 可以计算出 26 项的紊乱数是 26 的子阶乘（！26）

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

所以有关于2^87字母表的混乱是可能的。这里有一些用于计算随机紊乱的例程和一种生成连续紊乱的方法，而不像上面最初问题中引用的例程那样将它们全部存储在内存中。

于 2020-01-24T04:19:47.377 回答