Python: странное поведение функции добавления списка

Я новичок в Python.

Я пытаюсь сделать Kruskal algo. Вот мой код:

#c={('v','a'):5,('v','g'):5,('g','a'):5,('v','b'):7,('v','e'):4,('f','e'):8,('f','b'):8,('f','c'):11,('c','e'):9,('c','d'):7,('c','b'):9,('e','d'):8} #n=8 def argmin(c): m=1e100 r=() for i in c: if c[i]<m: m=c[i] r=i return r def kruskal (n, c): T=[] B=[] while len(T)<n-1: E=argmin(c) c.pop(E) e=[] e+=E a0=0 a1=0 f0=-1 f1=-1 cross=0 # print('e avant',e) for i in range(len(B)): for j in range(len(B[i])): if e[0]==B[i][j]: cross+=1 f0=i if e[1]==B[i][j]: cross+=1 f1=i if cross==2: break else: cross=0 if cross==2: continue # print('e apres',e) T.append(e) # print('T',T) if f0!=-1 and f1!=-1: B[f0].extend(B[f1]) B.pop(f1) elif f0!=-1: B[f0].extend(e[1]) elif f1!=-1: B[f1].extend(e[0]) else : B.append(e) # print('B', B) return T 

Проблема у меня в строке, где: «T.append (e)« В результате T [0] не то, что я ожидаю. если я введу следующее:

 c={('v','a'):5,('v','g'):5,('g','a'):5,('v','b'):7,('v','e'):4,('f','e'):8,('f','b'):8,('f','c'):11,('c','e'):9,('c','d'):7,('c','b'):9,('e','d'):8} n=8 

Затем я вызываю свою функцию: kruskal (8, c) Я получаю:

[['v', 'e', 'g', 'a', 'b', 'f', 'c', 'd'], ['v', 'g'], ['v', 'a'], ['v', 'b'], ['c', 'd'], ['f', 'b'], ['e', 'd']]

Где, как я ожидаю, следующее:

 [['v', 'e'], ['v', 'g'], ['v', 'a'], ['v', 'b'], ['c', 'd'], ['f', 'b'], ['e', 'd']] 

Не ищите весь ваш код. Но что-то найдено, что вы добавляете references на list sometime.So, чтобы просто исправить:

 from copy import deepcopy T.append(deepcopy(e)) #in place of T.append(e) 

Выдает результат как

 [['v', 'e'], ['g', 'a'], ['v', 'a'], ['v', 'b'], ['c', 'd'], ['f', 'b'], ['e', 'd']] 

пример

 a = [1, 2] b = a b.append(3) >>>a [1,2,3] >>>b [1,2,3] 

Что здесь происходит

 a = [1,2] b = a >>>id(a), id(b) (140526873334272, 140526873334272) 

Это список [1,2] tagged двумя переменными a и b . Таким образом, любые изменения в списке будут влиять на все varables помеченные им.

Ответ itzmeontv корректен в отношении основной причины вашей проблемы, первый член T является изменчивым списком, который вы затем изменяете далее в своем коде. Кодовый путь, почему это происходит в вашем случае, немного сложнее:

  1. На первой итерации через ваш алгоритм вы добавляете e в T – поэтому T[0] ссылается на имя списка e в этой точке (содержимое ['v','e'] )
  2. На этой же итерации вы всегда попадаете в этот блок:

      else : B.append(e) 
  3. Это означает, что B[0] теперь также относится к списку с именем e т. Е. T[0] относится к тому же списку, что и в B[0] и любые изменения в B[0] будут отражены в T[0] поскольку списки изменяемы.
  4. Затем следующая итерация создает новый eно список, упомянутый в B[0] и T[0] все еще тот же список, т. Е. ['v','e']
  5. Затем вы продолжаете расширять этот список, когда вы делаете B[f0].extend(B[f1]) в случаях, когда f0 равно нулю

Это признак назначения списка, не создающего копию в Python, подробное описание которого дается в этом вопросе, если вы хотите углубить свое понимание. Ряд опций добавления вашего списка в T задается вместе с таймингами – вы можете, например, написать T.append(e[:]) , с записью среза, неявно T.append(e[:]) копию e в точке вы добавляете его.

Одна вещь, которую вы, возможно, захотите рассмотреть, – это нужно, чтобы члены T были изменены после их добавления в T Если вы этого не сделаете – вариант может состоять в том, чтобы добавлять tuples а не lists т.е.

 T.append(tuple(e))