我试图在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)用以下内容填充lista
[1, 1]
[2, 1]
[1, 2]
[2, 2]

但是,当我试图创建长度为9(generatePermutations(1,9,9))的数组的排列时,在函数完成之前很长一段时间,我遇到了堆栈溢出错误。有什么办法可以防止这种情况发生吗?

最佳答案

我做了一些测试,我发现函数的设置方式,它为每个排列调用自己。如中所述,递归深度与到目前为止生成的置换数相同当您尝试执行generatePermutations(1,9,9)时,python会尝试递归到9!=362880级别deep,这太深了(它仅限于1000)。
相反,重构代码,以便在a中遍历每个元素,追加当前数字,并在每个数字的循环中执行此操作。这样,递归只需深入9层。

10-07 21:54
查看更多