Блог

Главная - Вопросы по программированию - Рекурсивная перестановка в Python

Рекурсивная перестановка в Python

#python #recursion

#python #рекурсия

Вопрос:

Мне нужно создать перестановки списка из 3 чисел [0, 1, -1] в расширяющемся списке.

Мой вывод:

 0
0,0  0,1  0,-1
0,0,0  0,0,1  0,0,-1
0,0,0,0  0,0,0,1  0,0,0,-1

Ожидаемый результат: все возможные перестановки размера списка N , но в моем коде изменяются только последние 3 числа 

 def rec(alist):
    print(alist)
    if len(alist) == 4:
        return (alist)
    if alist[-1] == 0 or len(alist) == 0:
        alist.append(1)
        return(rec(alist))
    if alist[-1] == 1:
        alist[-1] = -1
        return(rec(alist))
    if alist[-1] == -1:
        alist[-1] = 0
        return(rec(alist))

Комментарии:

1. Есть ли причина, по которой вам нужно сделать это самостоятельно? Вы смотрели на itertools.permutations ?

2. Можете ли вы опубликовать ожидаемый результат?

3. Крис нет, я взгляну

4. ожидаемый результат — это все возможные комбинации для списка, которые имеют номера [0,1-1], поэтому для длины списка 3 это будет [0,0,1] [0,1,0] [1,0,0] [0,1,1] [1,0,1] [1,1,1] [0,0-1] [1,-1,0] и многое другое

5. Вы хотите return все комбинации (возможно, в виде списка списков) или вы просто хотите их распечатать? Если вас интересует только печать результатов, я думаю, вы можете удалить большую часть return утвержденийst, но есть несколько других вариантов, если вы хотите каким-либо образом возвращать значения. Создание рекурсивного генератора довольно изящно, если вы понимаете, как они работают!

Ответ №1:

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

Существует множество различных способов сделать то, что вы ищете. Кажется, вы пытаетесь использовать хвостовую рекурсию (хотя это не дает никаких преимуществ в Python). Однако мы можем заставить это работать, используя дополнительный аргумент, чтобы сообщить коду, следует ли расширять список или нет (этого не следует делать, когда список заполнен или когда мы возвращаемся назад):

 def rec(lst, expand=True):
    if len(lst) == 4:
        print(lst)
        expand = False

    if expand:
        lst.append(1)
    elif lst[-1] == 1: # expand is False here and in the other elif/else clauses
        lst[-1] = -1
        expand = True
    elif lst[-1] == -1:
        lst[-1] = 0
        expand = True
    else: # lst[-1] == 0
        lst.pop()  # backtracking step
        # leave expand as False

    if lst:
        rec(lst, expand)

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

 def rec(lst):
    if len(lst) == 4:
        print(lst)
        return

    lst.append(1)
    rec(lst)

    lst[-1] = -1
    rec(lst)

    lst[-1] = 0
    rec(lst)

    lst.pop()

Обратите внимание, что в обоих этих решениях я ничего не возвращаю (что эквивалентно return None ) и только print добавляю результаты по мере их нахождения. Если вы хотите получить возвращаемые результаты, вам нужна более сложная логика. Генератор — это простой способ сделать это, просто измените print(lst) на yield lst и сделайте все рекурсивные вызовы yield from rec(lst) .

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

Ответ №2:

 import itertools
for p in itertools.product([0,1,-1], repeat=3):
    print (p)

Это декартово произведение множества на само себя