Проблемы начинающих со ссылками на массивы в Python 3.1.1

Question

В рамках последнего задания в классе программирования для начинающих на Python мне была назначена задача коммивояжера. Я остановился на рекурсивной функции, чтобы найти каждую перестановку и сумму расстояний между пунктами назначения, однако у меня много проблем со ссылками. Массивы в разных экземплярах функций Permute и Main TSP, похоже, указывают на одну и ту же ссылку.

from math import sqrt
    class TSP:
        def __init__(self):
            self.CartisianCoordinates = [['A',[1,1]], ['B',[2,2]], ['C',[2,1]], ['D',[1,2]], ['E',[3,3]]]
            self.Array = []
            self.Max = 0
            self.StoredList = ['',0]
        def Distance(self, i1, i2):
            x1 = self.CartisianCoordinates[i1][1][0]
            y1 = self.CartisianCoordinates[i1][1][1]
            x2 = self.CartisianCoordinates[i2][1][0]
            y2 = self.CartisianCoordinates[i2][1][1]
            return sqrt(pow((x2 - x1), 2) + pow((y2 - y1), 2))

    def Evaluate(self):
        temparray = []
        Data = []
        for i in range(len(self.CartisianCoordinates)):
            Data.append([])
        for i1 in range(len(self.CartisianCoordinates)):
            for i2 in range(len(self.CartisianCoordinates)):
                if i1 != i2:
                    temparray.append(self.Distance(i1, i2))
                else:
                    temparray.append('X')
            Data[i1] = temparray
            temparray = []
        self.Array = Data
        self.Max = len(Data)
    def Permute(self,varray,index,vcarry,mcarry): #Problem Class
        array = varray[:]
        carry = vcarry[:]
        for i in range(self.Max):
            print ('ARRAY:', array)
            print (index,i,carry,array[index][i])
            if array[index][i] != 'X':
                carry[0] += self.CartisianCoordinates[i][0]
                carry[1] += array[index][i]
                if len(carry) != self.Max:
                    temparray = array[:]
                    for j in range(self.Max):temparray[j][i] = 'X'
                    index = i
                    mcarry += self.Permute(temparray,index,carry,mcarry)
                else:
                    return mcarry
        print ('pass',mcarry)
        return mcarry
    def Main(self):
        out = []
        self.Evaluate()
        for i in range(self.Max):
            array = self.Array[:] #array appears to maintain the same reference after each copy, resulting in an incorrect array being passed to Permute after the first iteration.
            print (self.Array[:])
            for j in range(self.Max):array[j][i] = 'X'
            print('I:', i, array)
            out.append(self.Permute(array,i,[str(self.CartisianCoordinates[i][0]),0],[]))
        return out


SalesPerson = TSP()
print(SalesPerson.Main())

Буду очень признателен, если вы поможете мне в решении проблем, с которыми я сталкиваюсь. Спасибо.

Answer 1

Нарезка списка (используя [:], как вы делаете) не создает глубокую копию - она ​​создает поверхностную копию. Это означает, что если список содержит ссылки на другие списки, копия будет содержать те же ссылки - не ссылки на новые списки . Другими словами, копируется только сам список, а не его элементы или элементы.

Здесь вам нужна глубокая копия . Вместо

array = self.Array[:]

попробовать

array = copy.deepcopy(self.Array)

, для которого вам понадобится import copy.