Почему эта ошибка тайм-аута возникает в рекурсии? (Python) - PullRequest
Новая
       6

Почему эта ошибка тайм-аута возникает в рекурсии? (Python)

0 голосов
/ 03 марта 2020

Мне поручено найти все перестановки данной строки (например, для string = 'aab' return ['aab', 'aba', 'baa']), и я понимаю, что для решения этой проблемы необходима рекурсия , Мне все еще трудно обернуть голову вокруг рекурсии, поэтому, когда я запускаю это, я получаю ошибку тайм-аута. Может кто-нибудь сказать мне, что именно это вызывает? Некоторое время смотрел на это. спасибо! 

import numpy as np
per = []

def permutations(string):
    #permute
    if len(string) == 1:
        return string
    global per
    strList = list(string)
    lastElem = len(strList)-1
    for i in range(lastElem+1):
        if i==lastElem:
            return string
        else:
            strList[i], strList[i+1] = strList[i+1], strList[i]
            permutations(str(strList[i+1:]))
            strList[i], strList[i+1] = strList[i+1], strList[i]
    per.append(str(strList))
    ##REMOVE DUPLICATES##
    np.array(per)
    return np.unique(per)

1 Ответ

0 голосов
/ 03 марта 2020

Проблема в том, что вы передаете строковое представление списка в рекурсивных вызовах функции вместо того, чтобы присоединяться к каждому элементу списка. Например, когда strList = ['a', 'a', 'b'], str(strList) вернет "['a', 'a', 'b']". Вместо этого вы должны использовать ''.join(strList) для фактического получения "aab".

Эта проблема не требует использования рекурсии, фактически вы можете достичь результата в одной строке с помощью itertools.permutations. 

>>> set(''.join(x) for x in itertools.permutations('aab'))
{'aab', 'aba', 'baa'}

Но если вы хотите реализовать рекурсивную версию, вам также необходимо передать аргумент для текущего индекса строки, которую вы достигли. Есть много примеров в Интернете для решения этой конкретной проблемы, просто требуется быстрый поиск в Google, и, возможно, даже на SO.

...