Sticky index reference while inserting into 2D list in Python

While attempting to implement a function that produces all permutations given a list of integers, I’m seeing this behavior where the inserts are not occurring as expected.

My code:

def permute(nums):
    perms = [[]]
    for i in range(len(nums)):
        new_perms = perms * (i + 1)
        for j in range(len(new_perms)):
            new_perms[j].insert(j % len(perms), nums[i])
        perms = new_perms
    return perms

When calling permute([1, 2, 3]) I’m expecting the perms to grow like:

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

However, by the second iteration of the interior loop with new_perms: [[1], [1]] I’m expecting it to grow to [[2, 1], [1, 2]], instead I’m getting [[2,1],[2,1]] and then [[2,2,1],[2,2,1]]. On each iteration of the j loop, the number is getting inserted into the current j position of all values of the list simultaneously on each iteration. Not what I was trying to do or expecting.

Ultimately, the code outputs:

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

Either this is some subtle reference behavior (yay, learn something new!) or I’m just having a really dumb day ;) Any help appreciated.

PLEASE NOTE: I’m NOT asking for help with an alternate or optimal permutations function! I’m trying to figure out why this particular code is behaving in an unexpected way. Thank you.

Answer

Ok, learned a good one here. DEEPCOPY!

    import copy

    def permute(nums):
        perms = [[]]
        for i in range(len(nums)):
            len_perms = len(perms)
            old_perms = perms
            perms = []
            for _ in range(i+1):
                perms += copy.deepcopy(old_perms)
            for j in range(len(perms)):
                perms[j].insert(j // len_perms, nums[i])
        return perms