Имеется задача. Во время шифрования алгоритм принимает символы шифруемого текста по одному и заменяет этот символ на один другой символ. Кодировка состоит из m символов, поэтому можно считать, что текст представляет собой последовательность натуральных чисел, не превосходящих. Во время работы алгоритм шифрования поддерживает перестановку натуральных чисел от 1 до m. В начале работы перестановка тождественна. Когда алгоритму на вход поступает символ x, алгоритм заменяет его на номер позиции в перестановке (в 1-индексации), на которой находится символ x, а также переносит x в начало перестановки. Например, если в некоторый момент работы алгоритма перестановка символов в нём равна [3, 1, 2], а на вход подаётся символ 1, то символ 1 будет заменён на символ 2, поскольку 1 стоит в перестановке на второй позиции, а перестановка примет вид [1, 3, 2].
Я написал код:
def encrypt(disp):
res = []
for i in input().split():
pos = disp.index(int(i))
res.append(pos + 1)
disp = [disp[pos]] + disp[:pos] + disp[pos + 1:]
return res
На вход поступает начальное состояние перестановки. Например [1, 2, 3, 4]. Пример работы алгоритма: 2 1 2 3 1 3 1 -> 2 2 2 3 3 2 2. Проблема в том, что мой алгоритм не укладывается в отведенный лимит времени. Может, есть способы ускорить работу? Работа алгоритма станет понятней если его показать таблицей. Зашифруем слово 2 3 1 2 1 1 1. Пусть x - входная буква, p - состояние перестановки на момент вхождения, y - результат.