Python : 递归调用的执行计数

Question

我在学习 Python 3.x 时使用欧拉问题来测试我的理解。在我为每个问题拼凑出一个可行的解决方案后，我发现发布的解决方案非常有启发性，并且在我自己努力之后我可以 "absorb" 新的想法。我正在研究 Euler 024，我正在尝试一种递归方法。现在，我绝不相信我的方法是最有效或最优雅的，但是，我成功地生成了一整套排列，增加了价值（因为我从一个排序的元组开始）——这是我想要的输出之一.此外，为了找到列表中的百万分之一（这是我想要的另一个输出，但还不能得到），我试图计算每次创建排列时有多少，这就是我卡住的地方。换句话说，我想做的是每次到达基本情况时计算递归调用的次数，即完成的排列，而不是递归调用的总数。我在 Whosebug 上找到了一些非常清楚的计算递归调用执行次数的示例，但我没有运气将这个想法应用到我的代码中。到目前为止，我在尝试中遇到的问题基本上是关于 "passing back" 使用 return 语句的 "completed" 排列的计数。我认为我需要这样做，因为我的 for 循环创建 "stem" 和 "tail" 元组的方式。在高层次上，要么我无法让计数器递增（因此它总是以“1”或“5”出现），要么 "nested return" 只是在找到第一个排列后终止代码，具体取决于我把 return 放在哪里。任何人都可以帮助将计数插入我的代码吗？

首先是我在 SO 中找到的我正在尝试使用的 "counting" 代码：

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

    return recur(n-1, count+1)

print(recur(15))

接下来是我的排列代码，其中没有计数。我尝试了很多方法，但其中 none 有效。所以下面没有 "counting" ，只是在代码中我认为计数器需要递增的地方的注释。

#
# 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')

提前致谢，

克莱夫

Answer 1

你为什么不为此编写生成器？然后你可以停在第 n 项 ("drop while i < n")。

我的解决方案使用的是 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]))

Answer 2

由于您似乎已经理解了基本问题，但只是想了解递归是如何发生的，所以您需要做的就是传递一个变量，告诉您您在调用堆栈的哪个位置。您可以向函数添加第三个参数，并在每次递归调用时递增它：

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])

Python : 递归调用的执行计数

Python : Counting execution of recursive call

python

algorithm

recursion

counting