Failed to add element to nested lists-CodePudding

Background (not the subject of the question): I am trying to solve the problem of generating all paths of length 3 from a list of all paths of length two in a list (p2 in the code below).
To that end I want to store all pairs of indices (i,j) for which p2[i][1]==p2[j][0] and `p2[i][2]==p2[j][1] (a path of length 2 is defined by a sequence of 3 vertices)

Question:

I tried store the indices in 2D lists whose entries are initially empty list that are appended newly encountered indices, but what is generated is a 2D list whose entries are lists that contain all indices.

Can someone explain what is actually going on behind the curtains and how to correctly add the indices to the innermost lists?

# -*- coding: utf-8 -*-
"""
Created on Sun May 29 10:10:40 2022

@author: Manfred Weis
"""
# generare all unsorted 3-tuples
from itertools import permutations

n=4
p2 = list(permutations(range(n),3))


print('p2:')
print(p2)
print()

N = len(p2)

Rows = [[[]]*n]*n # create 3D list
Cols = [[[]]*n]*n # create 3D list

for i in range(N):
    print(str(i) ': Rows[' str(p2[i][1]) '][' str(p2[i][2]) ']')
    print(str(i) ': Cols[' str(p2[i][0]) '][' str(p2[i][1]) ']')
    (Rows[p2[i][1]][p2[i][2]]).append(i) # add to the most nested list
    (Cols[p2[i][0]][p2[i][1]]).append(i) # add to the most nested list
    
for i in range(n):
    for j in range(n):
        print(str(i) ',' str(j) ':')
        print(str(Rows[i][j]))
        print(str(Cols[i][j]))
        print()

CodePudding user response：

You are having a shallow copy problem when you initialize your Rows and Cols 3D lists. Instead of using multiplication, you need to initialize them like so:

for k in range(n):
    Rows.append([])
    Cols.append([])
    for l in range(n):
        Rows[k].append([])
        Cols[k].append([])

The problem with doing multiplication in order to initialize the 3D list of lists is that all n lists inside are all pointing to the same list, so when you append to one of them, you append to all of them, since they are technically only shallow copies of each other. Therefore, when you print them at the end, all the lists have all the numbers added to them, since they all point to the same place in memory. By initializing the 3D list using the method above, you are creating separate lists in separate locations in memory and you are inserting each of them into your Rows and Cols 3D lists.

Check out what happens when you do the following:

x = [[]]*2
x[0].append(5)

Output:

[[5], [5]]

But if you do the following, you solve the problem:

x = [[],[]]
x[0].append(5)

Output:

[[5], []]

Here are some other people's explanations which are better than mine:

List of lists changes reflected across sublists unexpectedly

Edit:

Here is a better more pythonic way to initialize Rows and Cols:

Rows = [[ [] for j in range(n)] for i in range(n)]
Cols = [[ [] for j in range(n)] for i in range(n)]