Замена цикла for хвостовой рекурсией в рекурсивной функции - PullRequest
Новая
       31

Замена цикла for хвостовой рекурсией в рекурсивной функции

0 голосов
/ 12 сентября 2018

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

def permutations(A):
    P = []
    P2 = []
    permutations_recursive(A, [], P)
    permutations_tail_recursive(A, [], P2, 0)
    print(P2)
    return P

def permutations_recursive(first, last, perms):
    if len(first) == 0:
        perms.append(last)
    else:
        for i in range(len(first)):
            permutations_recursive(
                first[:i] + first[i+1:],
                last + [first[i]],
                perms)

Ответы [ 2 ]

0 голосов
/ 12 сентября 2018

Полностью рекурсивная функция должна быть: 

def permutations_comp_recursive(first, last, perms, i):
    if len(first) == 0:
        perms.append(last)
    elif i == len(first):
        pass
    else:
        permutations_comp_recursive(first, last, perms, i+1)
        if first:
                permutations_comp_recursive(
                first[:i]+first[i+1:],
                last + [first[i]],
                perms, 0)

Для хорошей производительности я рекомендую numpy solutions .

Редактировать 1: Теперь следующее должно быть хвостово-рекурсивным, с использованием списочных представлений. Это использует workarount для хвостовой рекурсии в python (и последние 2 аргумента были опущены - результат передается как возвращаемое значение): 

import itertools as it
class Recurse(Exception):
    def __init__(self, *args, **kwargs):
        self.args = args
        self.kwargs = kwargs

def recurse(*args, **kwargs):
    raise Recurse(*args, **kwargs)

def tail_recursive(f):
    def decorated(*args, **kwargs):
        while True:
            try:
                return f(*args, **kwargs)
            except Recurse as r:
                args = r.args
                kwargs = r.kwargs
                continue
    return decorated

@tail_recursive
def permutations_tail_recursive(first, last, direct=False):
    if len(first) == 0 or not all(first):
        return last
    else:
        l = len(first[0]) if direct else len(first)
        if last:
            return recurse([fi[:i]+fi[i+1:] for fi, i in it.product(first, range(l))],
                [last[j] + first[j][i] for j, i in it.product(range(len(last)), range(l))], True)
        else:
            return recurse([first[:i]+first[i+1:] for i in range(l)],
                [first[i] for i in range(l)], True)

Это не оптимизировано и использует циклы. Я не уверен, что это и код без цикла выше могут быть объединены - может посмотреть на это снова. Для этого приложения можно использовать itertools.permutations.

0 голосов
/ 12 сентября 2018

Закрыть итерационный аналог: 

def permutations(A):
    P = []
    permutationsI(A, P)
    print(P)

def permutationsI(A, perms):
   stack = [(A, [])]
    while len(stack):
        first, last = stack.pop()
        if len(first):
            for i in range(len(first)):
                stack.append((first[:i] + first[i+1:],last + [first[i]]))
        else:
            perms.append(last)

permutations([1,2,3])
>>[[3, 2, 1], [3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 3, 2], [1, 2, 3]]
...