Цикл внутри рекурсивной функции не итерируется до конца Python

Question

Решаю задачу "Millipede of words". В функцию подается список слов. Функция должна вернуть True, если все слова списка можно соединить, чтобы последняя буква предыдущего слова была такой же, как и первая буква следующего слова. В обратном случае - False. Написал такой код:

def solution(arr):
    def recurtion(arr, letter):
        if len(arr) == 1:
            if arr[0][0] == letter:
                return True

        for i in range(len(arr)):
            if arr[i][0] == letter:
                return recurtion(arr[0:i] + arr[i+1:], arr[i][-1])

    for j in range(len(arr)):
        if recurtion(arr[0:j] + arr[j+1:], arr[j][-1]):
            return True
    return False

Идея в том, чтобы взять каждое отдельное слово из списка за первое, передать в рекурсивную функцию оставшийся список и последнюю букву первого слова, там перебираем все слова, если есть подходящее, то передаем в функцию его последнюю букву и оставшийся список и т.д. Если осталось одно слово и буквы совпадают, то возвращаем True, в обратном случае False. Но вот например на таком списке тест не проходит:

['tablet', 'endorse', 'transport', 'elephant', 'evaluate', 'embrace', 'empire']

Проблема в том, что цикл for в recurtion() не итерируется до конца, если какое либо слово подошло, то вызывается рекурсивная функция и по тем словам, которые идут дальше for почему-то больше не итерируется. Помогите, пожалуйста, разобраться. Если есть какие-либо замечания, напишите тоже, пожалуйста.

Answer 1

Задача не нова, на английском stackoverflow быстрее всего с данным массивом отработал этот ответ.

def solution(arr):
    return len(max(list(chains(arr)), key=len)) == len(arr)

def chains(words, previous_word_index=None):
    yield []
    if previous_word_index is not None:
        previous_letter = words[previous_word_index][-1]
        words = words[:previous_word_index] + words[previous_word_index + 1:]
    for i, each_word in enumerate( words ):
        if previous_word_index is None or each_word.startswith(previous_letter):
            for tail in chains(words, previous_word_index=i):
                yield [each_word] + tail

Вывод:

Wall time: 998 µs

True

Answer 2

Ваше решение зависит от порядка слов в списке:

['ab', 'bb', 'bс'] -> True
['ab', 'bс', 'bb'] -> False

Ошибка в этом фрагменте:

    for i in range(len(arr)):
        if arr[i][0] == letter:
            return recurtion(arr[0:i] + arr[i+1:], arr[i][-1])

Цикл проверяет только первое подходящее слово. Такие слова в примере - bb и bc. Отличается только порядок. Если первое bb, всё хорошо. Если - bc, рекурсивный вызов заканчивается неуспехом, но следующее слово не будет проверено.

Исправление. В случае неуспеха продолжается поиск среди оставшихся слов:

    for i in range(len(arr)):
        if arr[i][0] == letter:
            if recurtion(arr[0:i] + arr[i+1:], arr[i][-1]):
                return True

Оставшиеся недочёты, не ошибки.

recurtion возвращает True или None (то есть он ничего не возвращает, но Питон так устроен, что тогда возвращаемым значением становится пусто). return False в конце recurtion исправляет ситуацию.
if len(arr) == 1: - слишком рано срабатывает. Можно сделать код проще, если прекращать рекурсию, когда массив пуст:

    def recurtion(arr, letter):
        if not arr: # список пуст
            return True

        for i in range(len(arr)):
            if arr[i][0] == letter:
                if recurtion(arr[0:i] + arr[i+1:], arr[i][-1]):
                    return True

        return False

Поиск по словам есть в solution и в recurtion. Дублирование - не хорошо. Хотя циклы отличаются, их можно объединить с помощью str.startswith:

def solution(arr):

    def recurtion(arr, prefix):
        if not arr: # список пуст
            return True

        for i in range(len(arr)):
            if arr[i].startswith(prefix):
                if recurtion(arr[0:i] + arr[i+1:], arr[i][-1]):
                    return True

        return False

    return recurtion(arr, '')

recurtion -> recursion.

БЛОГ НА HUSL

Цикл внутри рекурсивной функции не итерируется до конца Python

Ответы (2 шт):

Вывод: