#python #recursion
#python #рекурсия
Вопрос:
У меня был класс по рекурсии и некоторым назначениям. Вот один, который я вообще не могу решить.
У нас есть список в следующем формате ['word','blabla','thing']
и число L в качестве входных данных.
Идея состоит в том, чтобы попытаться найти, есть ли способ объединить некоторые слова (или взять только одно), если количество символов / комбинаций слов равно L. Примечание: если у нас есть комбинация, то мы должны посчитать запятые (разделители) в общем количестве символов
Например: print(recursive_func(['word','blabla','thing'], 12))
должен вернуться True
.
Действительно, длина blabla равна 6, а длина thing равна 5, и у нас есть запятая, так что итого получается 12.
У меня есть следующий код :
def recursive_func(words, L):
if len(words) == 1 or len(words[-1]) == L:
return len(words[-1]) == L
last_word = words[-1]
without_last_word = words[:-1]
return ??? or ???
Итак, я понимаю код, потому что я делал аналогичный ранее, но я понятия не имею, что добавить к этим «???».
Поскольку речь идет о рекурсии, нам, очевидно, нужно указать что-то вроде recursive_func(without_last_word, L)
: я предполагаю, что необходимо уменьшить L на len(words[-1])
, а затем попробовать, есть ли совпадение.
Но я понятия не имею, как на самом деле это сделать, и я не могу правильно ее закодировать.
Не могли бы вы дать совет?
большое вам спасибо
Ответ №1:
Хитрость заключается в том, чтобы попытаться выбрать слово и посмотреть, существует ли решение с оставшимися словами. Если нет, то мы можем исключить это слово.
def recursive_func(words, L):
# A direct fit?
if any(len(w) == L for w in words):
return True
# We try the ith word w, and see if a combo solution exists
# including that word, otherwise we eliminate it.
for i, w in enumerate(words):
remaining_candidates = words[i 1:]
if recursive_func(remaining_candidates, L - len(w) - 1):
return True
return False
Комментарии:
1. Хотя ваша прямая проверка соответствия работает, более простым базовым вариантом было бы проверить, существует ли
L == 0
2. @Barmar Ты забываешь о запятой.
3. Ах да, при совпадении одного слова запятая отсутствует.
4. Нет необходимости добавлять циклы for (особенно 2 в каждой рекурсии). Это можно сделать с помощью самой рекурсии.
Ответ №2:
Если вам нужна комбинация любых слов, например, вы можете комбинировать 'word'
и 'thing'
переходить 'blabla'
из вашего примера, вы можете написать что-то вроде этого:
def recursive_func(words, L, used, cnt):
if (cnt == L):
return True
for i in range(len(words)):
if (not used[i]):
used[i] = True
if (recursive_func(words, L, used, len(words[i]) if cnt == 0 else cnt len(words[i]) 1)):
return True
used[i] = False
return False
recursive_func(words, L, [False] * len(words), 0)
где used
— массив, который знает используемые слова в текущей комбинации, cnt
— длина текущей комбинации.
Комментарии:
1. Изменение подписи для добавления информации не требуется, см. Мой ответ. Кроме того, перебор всех слов не требуется, если вы рекурсивно строите два дерева вместо одного.
Ответ №3:
Я бы сделал что-то вроде этого:
def recursive_func(words, L):
if sum(map(len, words)) len(words) - 1 == L:
return True
if len(words) == 1:
return False
for w in list(words):
words.remove(w)
if recursive_func(words, L):
return True
words.append(w)
return False
Сначала вы проверяете, удовлетворяет ли весь список условию, если нет, вы пытаетесь использовать подсписок.
Вы можете использовать itertools
или set
необязательно.
Ответ №4:
Это должно решить проблему. Мы строим 2 дерева (с первым словом и без него) в каждой рекурсии. Имейте в виду, что слова в комбинации могут не находиться рядом друг с другом.
s =["hi","hallo","du"]
def rec(words:list, L:int):
if not words:
return False
elif len(words[0]) == L:
return True
elif len(words[0]) > L:
return False #early stopping
return rec(words[1:], L-len(words[0])-1) or rec(words[1:],L) #all combinations with and without this word
print(rec(s, 4))