Sticky index reference while inserting into 2D list in Python

Question

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 1

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