0

Я написал программу для поиска палинграм в текстовом файле, состоящим из 100 тысяч слов. Каким образом можно ее изменить, чтобы эта же задача решалась с использованием рекурсии? Я прорешал много других задачек связанных с рекурсией, чтобы лучше ее понять, но в данной задаче решение в голову никак не приходит.

Для справки: Палинграмма - то же, что и палиндром, но состоит из нескольких слов и также читается одинаково слева направо.

Например: drowsy sword, denims mined, dairy raid, rise sir

import dictionary

word_list = dictionary.load("words.txt")

def find_palingrams():
    pali_list = []
    words = set(word_list)

    for word in words:
        end = len(word)
        rev_word = word[::-1]

        if end > 1:

            for i in range(end):

                # Является ли КОНЕЦ слова палиндромным, а НАЧАЛО -
                # перевернутым словом в списке слов (реальным словом)
                if word[i:] == rev_word[:end - i] and rev_word[end - i:] in words:
                    pali_list.append((word, rev_word[end - i:]))

                # Является ли НАЧАЛО слова палиндромным, а КОНЕЦ -
                # перевернутым словом в списке слов (реальным словом)
                if word[:i] == rev_word[end - i:] and rev_word[:end - i] in words:
                    pali_list.append((rev_word[:end - i], word))

    return pali_list

palingrams = find_palingrams()
6
  • 2
    а зачем в этой задаче рекурсия?
    – Zhihar
    29 сен 2022 в 12:32
  • согласен, текущий алгоритм хорош и так, но я хочу понять как эта же задача будет работать с использованием рекурсии, чтобы в целом лучше ее понимать
    – DarthVader
    29 сен 2022 в 12:37
  • 2
    а может она никак не будет работать с использованием рекурсии. Не каждую задачу можно применить рекурсией. Вы же не будете применять разводной ключ для завязывания шнурков, чтобы лучше понять, как он работает. Может и получится шнурки завязать, но понимания это вряд ли прибавит. 29 сен 2022 в 12:47
  • 1
    В принципе, любой цикл можно при желании заменить рекурсией, но не каждый нужно заменять.
    – insolor
    29 сен 2022 в 13:00
  • Если данный код проверяет на палинграмность только пары слов, то, возможно, с помощью рекурсии можно будет эффективно проверять сочетания из N слов? 29 сен 2022 в 13:34

1 ответ 1

0

чисто из спортивного интереса можно заменить внутренний цикл на рекурсию, тогда получится что-то такое:

def find_palingrams():
    pali_list = []
    words = set(word_list)
    
    def pali(suff, pref=''):
        if not suff: return None
        if pref[::-1] in words and suff==suff[::-1]: return pref+suff,pref[::-1]
        if suff[::-1] in words and pref==pref[::-1]: return suff[::-1],pref+suff
        return pali(suff[1:],pref+suff[0])
    
    for word in words:
        if p:=pali(word): pali_list.append(p)
                
    return pali_list


word_list = ['drowsy', 'sword', 'denims', 'mined', 'dairy', 'riad', 'rise', 'sir']
find_palingrams()
# [('rise', 'sir'), ('denims', 'mined'), ('drowsy', 'sword'), ('dairy', 'riad')]

как видно, лучше и короче не стало, а читабельность кода пострадала

1
  • Спасибо, мне как раз из спортивного интереса и было интересно)
    – DarthVader
    2 окт 2022 в 21:33

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.