Оптимизация рекурсии в python

Question

У меня проблемы с оптимизацией рекурсии на python. Поэтому я хочу сгенерировать все возможности в массиве / списке, состоящем из 10 элементов, которые могут быть заполнены числом 0-9 на каждом элементе. Итак, я решил использовать рекурсию в этом случае, вот:

routes = []
route = []

def generateRoutes(route, floor):
    if floor >= 10:
        routes.append(route)
    else:
        for channel in range(0, 10):
            new_route=route.copy()
            new_route.append(channel)
            generateRoutes(new_route, floor + 1)

generateRoutes(route, 0)

Мой код требует вечности, чтобы завершить задачу (не говоря уже о том, что занимает много памяти). У меня вопрос, есть ли способ решить / оптимизировать мой код? (Я также открыт для другого метода, кроме рекурсии)

Edit: Добавлена ​​информация о том, как функция называется

Answer 1

Уже есть нерекурсивное, ленивое решение, доступное через модуль itertools:

>>> import itertools
>>> routes = itertools.product(range(10), repeat=10)

Каждое значение генерируется по требованию, когда вы перебираете routes, а не сохраняете все 10 миллиардових в памяти сразу.

>>> print(list(itertools.islice(routes, 20)))
[(0, 0, 0, 0, 0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0, 0, 0, 0, 1), (0, 0, 0, 0, 0, 0, 0, 0, 0, 2), (0, 0, 0, 0, 0, 0, 0, 0, 0, 3), (0, 0, 0, 0, 0, 0, 0, 0, 0, 4), (0, 0, 0, 0, 0, 0, 0, 0, 0, 5), (0, 0, 0, 0, 0, 0, 0, 0, 0, 6), (0, 0, 0, 0, 0, 0, 0, 0, 0, 7), (0, 0, 0, 0, 0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0, 0, 0, 0, 9), (0, 0, 0, 0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 0, 0, 0, 1, 1), (0, 0, 0, 0, 0, 0, 0, 0, 1, 2), (0, 0, 0, 0, 0, 0, 0, 0, 1, 3), (0, 0, 0, 0, 0, 0, 0, 0, 1, 4), (0, 0, 0, 0, 0, 0, 0, 0, 1, 5), (0, 0, 0, 0, 0, 0, 0, 0, 1, 6), (0, 0, 0, 0, 0, 0, 0, 0, 1, 7), (0, 0, 0, 0, 0, 0, 0, 0, 1, 8), (0, 0, 0, 0, 0, 0, 0, 0, 1, 9)]
>>> print(list(itertools.islice(routes, 20)))
[(0, 0, 0, 0, 0, 0, 0, 0, 2, 0), (0, 0, 0, 0, 0, 0, 0, 0, 2, 1), (0, 0, 0, 0, 0, 0, 0, 0, 2, 2), (0, 0, 0, 0, 0, 0, 0, 0, 2, 3), (0, 0, 0, 0, 0, 0, 0, 0, 2, 4), (0, 0, 0, 0, 0, 0, 0, 0, 2, 5), (0, 0, 0, 0, 0, 0, 0, 0, 2, 6), (0, 0, 0, 0, 0, 0, 0, 0, 2, 7), (0, 0, 0, 0, 0, 0, 0, 0, 2, 8), (0, 0, 0, 0, 0, 0, 0, 0, 2, 9), (0, 0, 0, 0, 0, 0, 0, 0, 3, 0), (0, 0, 0, 0, 0, 0, 0, 0, 3, 1), (0, 0, 0, 0, 0, 0, 0, 0, 3, 2), (0, 0, 0, 0, 0, 0, 0, 0, 3, 3), (0, 0, 0, 0, 0, 0, 0, 0, 3, 4), (0, 0, 0, 0, 0, 0, 0, 0, 3, 5), (0, 0, 0, 0, 0, 0, 0, 0, 3, 6), (0, 0, 0, 0, 0, 0, 0, 0, 3, 7), (0, 0, 0, 0, 0, 0, 0, 0, 3, 8), (0, 0, 0, 0, 0, 0, 0, 0, 3, 9)]

Answer 2

Если я правильно понимаю ваш вопрос, то itertools - это именно то, что вам нужно. Скорее всего как то так:

import itertools
nums = list(range(0, 10))
routes = list(itertools.product(nums, LENGTH))

Чтобы исправить проблему с памятью, вы должны использовать ее в качестве генератора:

import itertools
nums = list(range(0, 10))
for route in itertools.product(nums, LENGTH):
    # YOUR_STUFF

И если вы действительно просто хотите перебрать номер, почему бы не сделать

for i in range(10**LENGTH):
    ...

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