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

Question

Во-первых, я использую python.

У меня есть список элементов под названием tier1, он выглядит так.

tier1 = ['a1','a2,'a3',..,'an']

У меня есть 2 функции: functionA и functionZ.

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

listOutput = functionA (tier1 [0]).

listOutput выглядит так:

listOutput = ['b1','b2,'b3',..,'bn']

В следующий раз functionA используется в listOutput, допустим элемент 'b1', он выдаст

listOutput = functionA('b1')

output:
listOutput = ['bc1','bc2,'bc3',..,'bcn']

На этот раз, когда используется functionA, скажем, 'bc1', он может оказаться пустым, поэтому functionZ используется на 'bc1' вместо этого, и вывод где-то хранится.

listOutput = functionA('bc1')

вывод

listOutput = []

Поэтому я использую

listOutput = functionZ('bc1')

вывод

listOutput = ['series1','series2','series3',....,'seriesn']

Теперь Я должен go вернуться и попробовать bc2, пока bcn не сделает то же самое logi c. Как только это будет сделано, я буду использовать functionA на «b2». и т. д.

Глубина каждого элемента может меняться.

Это выглядит примерно так

Пока listOutput не пуст, функция functionA должна использоваться для элементов listOutput или элементов tier1, пока не окажется пустым. Затем функция functionZ должна использоваться для любого элемента в списке, в котором functionA оказывается пустым.

После tier1 listOutput также всегда будет списком, который также должен циклически проходить по одному и тому же logi c необходимо использовать.

Я пытаюсь создать рекурсивную функцию на основе этого, но я застрял.

Пока что у меня есть,

def recursivefunction (idnum): #idnum will be one of the list items from tier1 or the listOutputs produced

    listOutput = functionA(idnum)

    if not listOutput:
        return functionZ(idnum)
    else:
        return recursivefunction(listOutput) 

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

Нужно ли мне создавать новый вид структуры данных? Понятия не имею, с чего начать, стоит ли мне искать какой-нибудь класс со связанными списками?

Answer 1

Как я понимаю вашу проблему:

• есть список ввода tier1, который представляет собой список строк
• есть две функции, A и Z
  • A, когда применяется к строке, возвращает список строк
  • Z, когда применяется к строке, возвращает некоторое значение (тип неясен, предположим также список строк)
• алгоритм:
  • для каждого элемента из tier1, применить A к элементу
  • , если результат - пустой список, вместо этого применить Z к элементу , без дальнейшей обработки
  • в противном случае, если результат не пустой, применить алгоритм из списка

Итак, в Python:

from random import randint
# since you haven't shared what A and Z do, 
# I'm just having them do random stuff that matches your description


def function_a(s):
    # giving it a 75% chance to be empty
    if randint(1, 4) != 1:
        return []
    else:
        # otherwise between 1 and 4 random strings from some selection
        return [['a', 'b', 'c'][randint(0, 2)] for _ in range(randint(1,4))]
        # in the real case, I'm sure the result depends on `s` but it doesn't matter


def function_z(s):
    # otherwise between 0 and 4 random strings from some selection
    return [['x', 'y', 'z'][randint(0, 2)] for _ in range(randint(0,4))]


def solution(xs):
    # this is really the answer to your question:
    rs = []
    for x in xs:
        # first compute A of x
        r = function_a(x)
        # if that's the empty list
        if not r:
            # then we want Z of x instead
            r = function_z(x)
        else:
            # otherwise, it's the same algorithm applied to all of r
            r = solution(r)
        # whatever the result, append it to rs
        rs.append(r)
    return rs


tier1 = ['a1', 'a2', 'a3', 'a4']

print(solution(tier1))

Обратите внимание, что function_a и function_z - это просто функции, генерирующие случайные результаты с типами результатов, которые вы указали. Вы не рассказали, что такое logi c для A и Z, поэтому сложно проверить, соответствуют ли результаты вам.

Однако функция solution делает именно то, что вы говорите. должен - если я правильно понимаю вас несколько сложное объяснение.

Учитывая, что решение вашего вопроса в основном таково:

def solution(xs):
    rs = []
    for x in xs:
        r = function_a(x)
        if not r:
            r = function_z(x)
        else:
            r = solution(r)
        rs.append(r)
    return rs

Что можно даже переписать на:

def solution_brief(xs):
    return [function_z(r) if not r else solution(r) for r in [function_a(x) for x in xs]]

Вам следует еще раз изучить описание вашей проблемы. Ключ к программированию - понять проблему и разбить ее на основные этапы. Как только вы это сделаете, код будет быстро следовать. Предпочитаете ли вы первое или второе решение, вероятно, это зависит от опыта и, возможно, от крошечной разницы в производительности.

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

def solution_iterative(xs):
    if not xs:
        return xs
    rs = xs.copy()
    stack_rs = [rs]
    stack_is = [0]
    while stack_rs:
        r = function_a(stack_rs[-1][stack_is[-1]])
        if not r:
            stack_rs[-1][stack_is[-1]] = function_z(stack_rs[-1][stack_is[-1]])
            stack_is[-1] += 1
        else:
            stack_rs[-1][stack_is[-1]] = r
            stack_rs.append(r)
            stack_is.append(0)
        while stack_is and stack_is[-1] >= len(stack_rs[-1]):
            stack_is.pop()
            stack_rs.pop()
            if stack_is:
                stack_is[-1] += 1
    return rs