在python中生成置换时如何防止堆栈溢出

Question

我试图在python中生成置换而不使用itertools。这是我迄今为止的代码：

def generatePermutations(minVal, maxVal, arrayLength, depth = -1, array = []):
    if(depth == -1): # set all values to minVal initially
        for i in range(arrayLength):
            array.append(minVal)
        depth += 1
        generatePermutations(minVal, maxVal, arrayLength, depth, array) # recurse

    elif depth < arrayLength:
        a.append(array[:]) # a is a list declared above the function

        current = 0
        while current <= depth:
            if array[current] < maxVal:
                array[current] += 1
                break
            else:
                if current < depth:
                    array[current] = minVal
                else:
                    depth += 1
                    array[current] = minVal
                    if depth < arrayLength:
                        array[depth] += 1
                    break
            current += 1

        generatePermutations(minVal, maxVal, arrayLength, depth, array)

该函数适用于足够小的一组数字。例如，generatePermutations(1,2,2)用以下内容填充列表a：

[1, 1]
[2, 1]
[1, 2]
[2, 2]

但是，当我尝试创建长度为9（generatePermutations(1,9,9)）的数组的置换时，我在函数完成之前就遇到了堆栈溢出错误。有什么办法可以防止这种情况发生吗？你知道吗

Answer 1

我做了一个小测试，我发现你的函数的设置方式，它自己调用每一个排列。如中所示，递归深度与迄今为止生成的置换数相同。当您尝试执行generatePermutations(1,9,9)时，Python会尝试递归到9!=362880深的级别，这太深了（仅限于1000）。你知道吗

相反，重构您的代码，这样您就可以迭代a中的每个元素，附加当前的数字，并对每个数字进行循环。这样，递归只需深入9层。你知道吗