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! Перестановки, а затем найдите одну * (s) с реальными словами, но я почти уверен, что вы имеете в виду виртуальный шифр, и в этом случае вы берете все первые наборы перестановок и выкладываете их в ряды аналогичной фракции и находите эти перестановки, а затем перекрестная проверка словарных слов, и тогда вы, вероятно, получите очень длинный список возможных сообщений, и вам придется перебирать те из них, которые имеют смысл.