#python #recursion #startswith
#питон #рекурсия #начинается с
Вопрос:
Эта программа должна возвращать значение True, если возможно сгенерировать заданную последовательность x
из заданного списка сегментов seglist
. После нахождения одного возможного решения это должно прекратиться.
Я попытался заменить и изменить расположение команд возврата, но всегда возникает другая проблема.
def valid_sequence(x, seglist): if x in seglist: return True for i in seglist: if x.startswith(i): return valid_sequence(x[len(i):], seglist) return False
Это возвращает правильное логическое значение для последовательности 'abc'
и списка ['a', 'ab', 'bc', 'c']
сегментов , ['a', 'b', 'c']
, и ['ab', 'bc']
, но не для списка ['a', 'ab', 'c']
сегментов , потому что, очевидно, он проходит через 'a'
вариант, но не будет успешным и останавливается перед прохождением 'ab'
, что и должно быть.
Я прогнал его через pythontutor и понял некоторые проблемы, но не смог определить, как их исправить.
Как мне написать его так, чтобы он продолжался с сегментом 'ab'
после неудачного пути 'a'
? Может быть, я упускаю что-то еще, учитывая, что я не могу понять эту рекурсию.
Возможно ли это хотя бы отдаленно таким образом, или мне нужно использовать совершенно другой подход?
Ответ №1:
Вы были очень близки в этом вопросе. Основная проблема заключается в том, что вы не должны немедленно возвращаться на рекурсивном шаге. Обратите внимание, что он вернется False
после первого вызванного цикла. Следовательно, вся функция False
также вернется.
Сказав это, вы должны вернуться только в том случае, если результат верен:
def valid_sequence(x, seglist): if x in seglist: return True for i in seglist: if x.startswith(i): if valid_sequence(x[len(i):], seglist): return True return False
Это устранит проблему, о которой вы упомянули, но есть еще одна, которую нужно решить. Если x = 'abc'
и seglist = ['ab', 'b', 'c']
функция будет правильно возвращена True
. Но он также вернется True
за x = 'abbc'
, x = 'abbbc'
и так далее. Это происходит потому, что буква » в » используется неопределенно. Я полагаю, что это нежелательное поведение. Чтобы преодолеть это, мы создаем копию списка для новых вызовов и удаляем используемый элемент:
import copy def valid_sequence(x, seglist): if x in seglist: return True for i in seglist: if x.startswith(i): newlist = copy.deepcopy(seglist) newlist.remove(i) if valid_sequence(x[len(i):], newlist): return True return False
Комментарии:
1. Большое вам спасибо! Да, это все исправило! И что касается второго предложения, я думаю, что на самом деле в этом нет необходимости, но это здорово знать!
Ответ №2:
Проблема с вашим кодом, как вы правильно определили, заключается в том, что ваша программа преждевременно возвращает False, прежде чем она исчерпает все возможные варианты строк в каждой позиции.
В частности, он возвращает значение False при запуске следующей строки:
return valid_sequence(x[len(i):], seglist)
Если вы подумаете об этом, программа никогда не сможет вернуть значение False в этом месте, поскольку она потенциально не закончила перебор всех строк seglist
. Однако вы хотите вернуть значение True, если он нашел строку выбора, которая завершает последовательность.
К счастью, для устранения этой проблемы требуется лишь небольшое изменение: убедитесь, что возвращаемое значение является истинным, прежде чем возвращать его. Я включил измененный код ниже.
def valid_sequence(x, seglist): if x in seglist: return True for i in seglist: if x.startswith(i): if valid_sequence(x[len(i):], seglist): return True return False
Комментарии:
1. альтернативно
def valid_sequence(x, seglist): return x in seglist or any(x.startswith(i) and valid_sequence(x[len(i):], seglist) for i in seglist)
2. Хотя лично я считаю
x == ''
, что это был бы лучший базовый вариант, чемx in seglist