Как разделить строки с помощью рекурсии в Python?

Question

Я хотел спросить, как создать рекурсивную функцию, которая разбивает каждую строку, содержащуюся в списке, для каждого символа, удаляя по одной из начала каждый раз, когда я повторяю процесс. Я тоже хочу сделать это, но удаляя письмо с конца каждый раз. например, если у меня есть что-то вроде:

list=['house','cat','dog']

я должен получить

['house','ouse','use','se','e','cat','at','t','dog','og','g']

и

['house','hous','hou','ho','h','cat','ca','c','dog','do','d']

Я пытался сделать это, но это не работает; Кроме того, все это должно быть рекурсивным ... заранее спасибо.

def substring(stringslist):
    final=[]
    for string in stringslist:
        if len(string)==1:
            return final.append(string)
        else:
            return final.append(substring(string[::-1]))

Answer 1

Во-первых, давайте исправим вашу функцию в итеративной версии, которая работает.

def substring(strings):
    final = []
    for string in strings:
        while string:
            final.append(string)
            string = string[1:]
    return final

Далее, давайте переместим переменную final в аргументы, чтобы рекурсивные вызовы функции могли основываться на списке.

def substring(strings, final=None):
    if final is None: final = []
    for string in strings:
        while string:
            final.append(string)
            string = string[1:]
    return final

Следующий шаг - преобразование for l oop в рекурсию. Мы можем видеть, что базовый случай - это когда список strings пуст, а рекурсивный случай должен работать с каждым элементом strings. Для рекурсивного случая здесь мы извлечем первый элемент strings и передадим остальную часть списка рекурсивному вызову.

def substring(strings, final=None):
    if final is None: final = []
    # base case: empty list
    if not strings: return final
    # recursive case:
    # work on first string in list
    string = strings[0]
    # add all substrings to final
    while string:
        final.append(string)
        string = string[1:]
    return substring(strings[1:], final)

Преобразование while l oop в рекурсию аналогичный процесс: найдите базовый случай (пустой string) и рекурсивный случай (добавив одну подстроку к final) и сделайте рекурсивный вызов для рекурсивного случая.

def substring(strings, final=None):
    if final is None: final = []
    if not strings: return final
    string = strings[0]
    if not string: return substring(strings[1:], final)
    final.append(string)
    strings[0] = string[1:]
    return substring(strings, final)

И, наконец, немного очистки.

def substring(strings, final=None):
    if final is None: final = []
    if not strings: return final
    if not string[0]: return substring(strings[1:], final)
    final.append(string)
    strings[0] = string[0][1:]
    return substring(strings, final)

Answer 2

Следующий код должен работать для вас:

list=['house','cat','dog']
final=[]

for word in list:
    for i in range(len(word)):
        final.append(word[i:])

print(final)

output: ['house', 'ouse', 'use', 'se', 'e', ​​'cat', 'at', 't', 'dog', 'og', 'g']

Здесь я перебираю список, и для каждого слова в списке я снова перебираю буквы для определения количества элементов, которые будут добавлены в окончательный список.

Answer 3

Если вы хотите рекурсию, это сделает работу. Я написал это только для одного случая, но вы можете легко перевернуть его для другого.

def substring(stringslist):
    final = []
    for string in stringslist:
        final.append(string)
        if len(string)==1:
            return final
        else:
            final.extend(substring([string[:-1]]))

    return final

Answer 4

Использование генератора упрощает реализацию - вам просто нужно привести результат к list().

lst=['house','cat','dog']

def substring(string, reversed=False):
    if string:  # if string is not zero-length:
        yield string  # yield its full length
        yield from substring(string[:-1] if reversed else string[1:])  # and recurse

def substrings(stringslist, reversed=False):
    for string in stringslist:
        yield from substring(string, reversed)

>>> list(substrings(lst))
['house', 'ouse', 'use', 'se', 'e', 'cat', 'at', 't', 'dog', 'og', 'g']
>>> list(substrings(lst, reversed=True))
['house', 'hous', 'ous', 'us', 's', 'cat', 'ca', 'a', 'dog', 'do', 'o']

Answer 5

Вот рекурсивный способ сделать это для одной строки, и я добавил для l oop, вы можете получить вдохновение от этого:

L = ['house','cat','dog']
final = []
def substring(s):
    global final
    if len(s)==1:
        final.append(s)
    else:
        final.append(s)
        substring(s[:-1])
    return final

for s in L:
    substring(s)
print(final)
# ['house', 'hous', 'hou', 'ho', 'h', 'cat', 'ca', 'c', 'dog', 'do', 'd']

Answer 6

Я использовал вложенные циклы for для ясности, но вы можете использовать списки для более короткого кода.

Используйте enumerate () для получения индекса, чтобы вы могли выполнять манипуляции с подстрокой.

IDLE Выход:

>>> new_list1 = []
>>> new_list2 = []
>>> for item in my_list:
        for index, value in enumerate(item):
            new_list1.append(item[:len(item)-index])
            new_list2.append(item[index:])


>>> new_list1
['house', 'hous', 'hou', 'ho', 'h', 'cat', 'ca', 'c', 'dog', 'do', 'd']
>>> new_list2
['house', 'ouse', 'use', 'se', 'e', 'cat', 'at', 't', 'dog', 'og', 'g']