Python: подсчет выполнения рекурсивного вызова

Question

Я использую проблемы Эйлера для проверки своего понимания при изучении Python 3.x. После того, как я собрал рабочее решение для каждой проблемы, я нахожу опубликованные решения очень полезными и могу "впитывать" новые идеи после того, как я боролся с собой. Я работаю над Euler 024, и я пытаюсь рекурсивный подход. Теперь я ни в коем случае не верю, что мой подход является наиболее эффективным или наиболее элегантным, однако я успешно генерирую полный набор перестановок, значение которых увеличивается (потому что я начинаю с отсортированного кортежа), что является одним из желаемых результатов., Кроме того, чтобы найти миллионную единицу в списке (это другой вывод, который я хочу, но пока не могу получить), я пытаюсь подсчитать, сколько их каждый раз, когда я создаю перестановку, и вот где я застреваю. Другими словами, я хочу подсчитать количество рекурсивных вызовов каждый раз, когда я достигаю базового случая, т.е. завершенную перестановку, а не общее количество рекурсивных вызовов. Я нашел в Stackru несколько очень четких примеров подсчета количества выполнений рекурсивных вызовов, но мне не повезло применить эту идею к моему коду. По сути, мои проблемы в моих попытках до сих пор связаны с "передачей" счетчика "завершенных" перестановок с использованием оператора return. Я думаю, что мне нужно сделать это, потому что мой цикл for создает кортежи "stem" и "tail". На высоком уровне, либо я не могу получить счетчик приращения (поэтому он всегда появляется как "1" или "5"), либо "вложенный возврат" просто завершает код после того, как найдена первая перестановка, в зависимости от того, где Я ставлю возврат. Может кто-нибудь помочь вставить подсчет в мой код?

Сначала "подсчитывающий" код, который я нашел в SO, который я пытаюсь использовать:

def recur(n, count=0):
    if n == 0:
        return "Finished count %s" % count

    return recur(n-1, count+1)

print(recur(15))

Далее мой код перестановки без учета в нем. Я перепробовал много подходов, но ни один из них не работает. Таким образом, следующее не имеет никакого "счета", это просто комментарий, и в этот момент в коде я считаю, что счетчик должен быть увеличен.

#
# euler 024 : Lexicographic permutations
#
import time
startTime= time.time()
#
def splitList(listStem,listTail):

    for idx in range(0,len(listTail)):
        tempStem =((listStem) + (listTail[idx],))
        tempTail = ((listTail[:idx]) + (listTail[1+idx:]))

        splitList(tempStem,tempTail)
    if len(listTail) ==0:
        #
        # I want to increment counter only when I am here
        #
        print("listStem=",listStem,"listTail=",listTail)

#
inStem = ()
#inTail = ("0","1","2","3","4","5","6","7","8","9")
inTail = ("0","1","2","3")

testStem = ("0","1")
testTail = ("2","3","4","5")

splitList(inStem,inTail)
#
print('Code execution duration : ',time.time() - startTime,' seconds')

Заранее спасибо,

Clive

Answer 1

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

def splitList(listStem, listTail, count):   
    for idx in range(0,len(listTail)):
        ...
        splitList(tempStem, tempTail, count)

    if len(listTail) == 0:
        count[0] += 1
        print('Count:', count)
        ...

Теперь вызовите эту функцию так (как и раньше):

splitList(inStem, inTail, [0])

Answer 2

Почему бы тебе не написать генератор для этого? Тогда вы можете просто остановиться на nth-й элемент ("брось, пока я

Мой раствор использует itertools, но вы можете использовать свой собственный генератор перестановок. Просто yield следующий элемент последовательности вместо его печати.

from itertools import permutations as perm, dropwhile as dw
print(''.join(dw(
    lambda x: x[0]<1000000, 
    enumerate(perm('0123456789'),1)
).__next__()[1]))