Блог

У меня был класс по рекурсии и некоторым назначениям. Вот один, который я вообще не могу решить.

У нас есть список в следующем формате ['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]) , а затем попробовать, есть ли совпадение.

Но я понятия не имею, как на самом деле это сделать, и я не могу правильно ее закодировать.

Не могли бы вы дать совет?

большое вам спасибо

Хитрость заключается в том, чтобы попытаться выбрать слово и посмотреть, существует ли решение с оставшимися словами. Если нет, то мы можем исключить это слово.

 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
 

Если вам нужна комбинация любых слов, например, вы можете комбинировать '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 — длина текущей комбинации.

Я бы сделал что-то вроде этого:

 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 необязательно.

Это должно решить проблему. Мы строим 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))