CODEWITHSUNDEEP
pythonstack-overflowpermutation
hmir
hmir

Reputation: 1413

How to stop the stack from overflowing when generating permutations in python

I'm trying to generate permutations in python without using itertools. This is my code thus far:

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)

The function works for a small enough set of numbers. For example, generatePermutations(1,2,2) populates list a with the following:

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

But, when I try to create permutations of an array of length 9 (generatePermutations(1,9,9)), then I run into a stack overflow error long before the function is finished. Is there any way of preventing this?

Upvotes: 4

Views: 156

Answers (1)

El&#39;endia Starman
El&#39;endia Starman

Reputation: 2244

I did a little testing, and I found that the way your function is set up, it calls itself for every single permutation. As in, the recursion depth is the same as the number of permutations generated so far. When you try to do generatePermutations(1,9,9), Python tries to recurse to 9!=362880 levels deep, which is far too deep (it's limited to 1000).

Instead, refactor your code so that you iterate over each element in a, appending the current digit, and do this in a loop for each digit. This way, the recursion will only have to go 9 levels deep.

Upvotes: 3

Related Questions