Минимальное количество преобразований для перехода от одного списка целых чисел к другому

Учитывая списки последовательностей P и T. Я пытаюсь написать алгоритм (функция minNumOfTransformations(P,T) ), которая возвращает минимальное количество перемещений или преобразований, необходимых для перехода к T из P. Эти преобразования включают замену, вставку или удаление. Например. чтобы добраться до [0,2,4,5] из [0,1,2,3,5] требуется как минимум 2 преобразования; Добавление 1 и замена 4 на 3. Я пытаюсь сделать это с помощью динамического программирования на python.

def minNumOfTransformations(P, T):


# If first list is empty, the only option is to 
# insert all the elements
if m==0: 
     return n 

# If second list is empty, the only option is to 
# remove all the characters of the first list 
if n==0: 
    return m 

# approach here is to solve simpler sub problems but this is where I get stuck 
if P[m-1]==T[n-1]: 
    return minNumofTransformations(P[m-1], T[n-1]) 

Ну и какой у тебя вопрос?

Thierry Lathuille 22.05.2019 16:43

пожалуйста, предоставьте весь ваш код. Оба m и n определены вне вашего вопроса (предположительно?).

Eric 22.05.2019 16:45
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения текстовых сообщений может быть настолько сложным или простым, насколько вы его сделаете. Как и в любом ML-проекте, вы можете выбрать...
7 лайфхаков для начинающих Python-программистов
7 лайфхаков для начинающих Python-программистов
В этой статье мы расскажем о хитростях и советах по Python, которые должны быть известны разработчику Python.
Установка Apache Cassandra на Mac OS
Установка Apache Cassandra на Mac OS
Это краткое руководство по установке Apache Cassandra.
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
В одном из недавних постов я рассказал о том, как я использую навыки количественных исследований, которые я совершенствую в рамках программы TPQ...
Создание персонального файлового хранилища
Создание персонального файлового хранилища
Вы когда-нибудь хотели поделиться с кем-то файлом, но он содержал конфиденциальную информацию? Многие думают, что электронная почта безопасна, но это...
Создание приборной панели для анализа данных на GCP - часть I
Создание приборной панели для анализа данных на GCP - часть I
Недавно я столкнулся с интересной бизнес-задачей - визуализацией сбоев в цепочке поставок лекарств, которую могут просматривать врачи и...
0
2
74
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Что мешает вам найти готовый ответ в Google, так это, вероятно, то, что вы не знаете, что то, что вы ищете, известно как расстояние Левенштейна и является стандартной метрикой для различия между последовательностями.

Существует Пакет Python, созданный специально для этого и реализованный на C, поэтому он, вероятно, будет быстрее, чем все, что вы напишете.

Если вы действительно хотите сделать это самостоятельно на Python, это поможет:
https://rosettacode.org/wiki/Levenshtein_distance#Python

Спасибо. Для подхода динамического программирования в Google указано, что временная сложность составляет O (нм). Вы знаете, почему это так?

Lstan14 23.05.2019 03:17

Другие вопросы по теме