Python-сообщество

Задача звучит следующим образом:
Преобразование Барроуза-Уилера выполняется в три этапа:
1. Составляется таблица всех циклических сдвигов входной строки.
2. Производится лексикографическая (в алфавитном порядке) сортировка строк таблицы. Лексикографическая сортировка происходит в соответствии с кодировкой Unicode.
3. В качестве выходной строки выбирается последний столбец таблицы преобразования и номер строки, совпадающей с исходной.
Напишите программу, которая делает обратное преобразование Алгоритма Барроуза-Уилера. Алгоритм заключается в разбиении входной строки (уже преобразованной алгоритмом) на последовательность символов, которые записываюся в столбик (добавление 1). Образованные строки лексикографически (unicod) сортируются (сортировка 1), а после к полученному добавляют слева символы из добавления 1 (добавление 2). Снова сортируют, продолжая таким образом, пока количество символов в полученных строках не станет равным количеству символов во входной строке. При любом добавлении добавляем символы из первого столбца. В конце образуется столбец, где искомая строка это строка c символом конца строки ‘|’.
**Входные данные:** строка, зашифрованная алгоритмом Барроуза-Уилера, длиной до 100 символов
**Пример входных данных:** |_deipPPier
**Выходные данные:** расшифрованная строка
**Пример выходных данных:** Pied_Piper|

С приведенным выше примером у меня все работает. Но если входная строка “BNNZAA|Aier”, то выводит “|ZBANANAer|”, что неправильно, потому что пропала “i”. Путем вывода промежуточных результатов и решения вручную я поняла, что это происходит из-за того, что порядок буквы “i” в столбце дополнения совпадает с её порядком в отсортированном столбце. То есть одна из строк получившейся матрицы “iiiiiiiiiii”, что выбрасывает её.

Подскажите, пожалуйста, как это можно пофиксить. У меня в коде может ошибка или это алгоритм нуждается в доработке?
Прямой код (вроде работает правильно):

 import sys
def transformation(input):
    if len(input) == 0:
        return None
    cycle_list = sorted([input[i+1:]+input[:i+1] for i in range(len(input))])
    output = ""
    for s in cycle_list:
        output += s[len(s)-1]
    return output
if __name__ == '__main__':
    for line in sys.stdin:
        print(transformation(line[:-1]))

 import sys
def re_transformation(input):
    if len(input) == 0:
        return None
    re_cycle_list = ["" for s in input]
    while len(re_cycle_list[0]) < len(input):
        re_cycle_list = sorted([input[i]+re_cycle_list[i] for i in range(len(input))])
    for s in re_cycle_list:
        if s[len(s)-1] == '|':
            return s
if __name__ == '__main__':
    for line in sys.stdin:
        print(re_transformation(line[:-1]))

Отредактировано wolfram18 (Март 7, 2024 12:16:09)