permutation in python: maximum recursion depth exceeded

Question

I am trying to generate permutation numbers using code I adapted from functioning C++. The Python version errs with

Line 42: RuntimeError: maximum recursion depth exceeded

for the input [5,4,6,2].

class Solution:
    # @param {integer[]} nums
    # @return {integer[][]}
    def permute(self, nums):
        result = []

        if len(nums) == 0:
            return result

        if len(nums) == 1:
            result.append(nums)
            return result

        if len(nums) == 2:
            result.append(nums)
            a = nums[0]
            b = nums[1]
            newrow = [b,a]
            result.append(newrow)
            return result

        for i in range(0, len(nums)):
            temp = nums
            fixvalue = temp[i]
            del(temp[i])
            tempresult = self.permute(temp)

            for j in range(0, len(tempresult)):
                tempresult[j].insert(0,fixvalue)
                result.append(tempresult[j])

        return result

Your solution doesn't work for input `[1, 2, 3]`. – Blender Jun 15 '15 at 23:28 — Blender, Jun 15 '15 at 23:28

score 2 · Accepted Answer · edited May 23 '17 at 12:14

2

Your recursion is actually adding elements to the list through the line

tempresult[j].insert(0,fixvalue)

You need to change the line

temp = nums

to

temp = nums[:]

This will create a copy of the input using copy-by-slice. Your present code is manipulating the original.

Unrelatedly, I'm not sure at all why you have a Java-esque class Solution containing permute without any state at all. Why not simply use permute as a function? What does the class add?

edited May 23 '17 at 12:14

Community

1
1

answered Jun 15 '15 at 23:30

Ami Tavory

74,578
11
141
185

thanks, you are right. after changing that line, the program works! – zxwjames Jun 15 '15 at 23:34

score 2 · Answer 2 · answered Jun 15 '15 at 23:37

The logic of your code has several errors regarding its manipulation of the lists. I'm actually a bit surprised by the error you're getting, as I would have thought an IndexError would be more likely, but it turns out you're adding new values to your lists as often as you're removing them.

Here's the core of the error:

temp = nums

This doesn't do what you expect if you're coming from C or C++. It doesn't copy the list stored in the nums variable and store the copied data as temp. It just creates a reference to the same list object. When you later modify temp (with del, and in some confusing corner cases, with insert), you're modifying nums as well.

You should think of assignments in Python as being like pointer assignments in C. Two pointers can refer to the same point in memory, and modifying that memory through one of them will affect what you see when you read the memory through the other pointer.

As for how to solve the issue, you will probably have better luck if you copy the contents of your nums list in some way. You can either use list or a slice nums[:] to copy the whole thing before using del to modify the copy, or you could use two smaller slices to get the values you want directly (nums[:i] + nums[i+1:]).

NeoWang · Answer 3 · 2015-06-16T05:37:39.033

If you just need permutations, python provides a out-of-box solution in itertools.permutations.

If you want to do this as an exercise, there are several problems with your code:

You have to make a copy of the list before recursion
Your recursion algorithm needs a special case for empty list, or list with one item, otherwise it won't exit, hence the recursion limit is exceeded.

If you correct your algorithm, and it still exceeds the recursion limit, you can change the recursion limit (default 1000) with:

sys.setrecursionlimit(10000)

My suggestion is to take a look at the official implementation in itertools.

permutation in python: maximum recursion depth exceeded

3 Answers3