python list scope across recursive call

Question

I wrote a recursive permutation generator in python3:

    def permute(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """

    ret = []
    n = len(nums)
    def dfs(temp, visited):
        if len(temp) == n:
            ret.append(temp[:])
            return
        for i in range(n):
            if not visited[i]:
                visited[i] = True
                temp.append(nums[i])
                dfs(temp, visited)
                # Cannot be:
                # temp = temp[:-1]
                del temp[-1]
                visited[i] = False
    dfs([], [False for _ in range(n)])                            
    return ret

I originally used temp = temp[:-1] after the recursive dfs returned but that does not seem to work. Explicitly using del temp[-1] worked.

I can't figure out why this is the case, could anyway please explain?

Can you fix the indentation in your code block ? Please update the question with sample input, expected output, and actual output. — Edwin van Mierlo
– Edwin van Mierlo, Commented May 3, 2018 at 17:29

Alex Hall · Accepted Answer · 2018-05-03 17:32:39Z

2

Assigning to a local variable inside a function has no effect on the outside world:

def foo(lst):
    lst = [1, 2, 3]

L = [1]
foo(L)
print(L)  # still [1]

Modifying a passed in variable does:

def foo(lst):
    lst.append(4)

L = [1]
foo(L)
print(L)  # [1, 4]

In your case, del temp[-1] changes the list that is being passed around. In your code there is only ever one list that is assigned to temp, which starts out as []. temp = temp[:-1] creates a new independent list.

answered May 3, 2018 at 17:32

Alex Hall

36.2k5 gold badges63 silver badges98 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

python list scope across recursive call

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related