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個すべてを試すだけです。順列を見つけて、実際の単語で1つ*（'s）を見つけますが、ヴィジュネル暗号を意味していると確信しています。この場合、最初の順列のセットをすべて取得し、それらを同様の派閥の行に配置して、それらの順列を調べてから辞書の単語をクロスチェックすると、考えられるメッセージの非常に長いリストが表示される可能性があり、意味のあるメッセージを並べ替える必要があります。

于 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 に答える