Rational number generator (Python)

Question

1. Почему он избавляется от записи [1,3], [3,2] и заменяет его на [2,3], [3,1]?

2. Примечание. [2,3], [3,1] - правильная ветвь, но она не должна отменять предыдущую запись, она должна быть добавлена ​​к ней.

   def rational(): 
       treecount = 0 
       tree = [[[1,1]]] 
       left=[0,0] 
       right=[0,0] 
       while(True): 
        treecount+=1 
        tree.append([]) 
        left=[0,0] 
        right=[0,0] 
        for z in range(len(tree[treecount-1])): 
         left[0] = tree[treecount-1][z][0] 
         right[0] = tree[treecount-1][z][0] + tree[treecount-1][z][1] 
         left[1] = tree[treecount-1][z][1] + tree[treecount-1][z][0] 
         right[1] = tree[treecount-1][z][1] 
         tree[treecount].append(left) 
         tree[treecount].append(right) 
         yield(tree) 
   

Выход выглядит следующим образом:

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

Answer 1

Вы работаете в фундаментальном аспекте объектной модели языка Python, а именно, что Python никогда не делает копии объектов неявно.

В вашем коде вы создаете два новых списка left и right непосредственно перед входом в цикл for. Затем вы повторно изменяете эти два списка и добавляете их к своему дереву до сих пор. Это нормально, за исключением того, что все, что вы делаете, добавляет ссылки на одинаковые два списка повторно.

Вот более простой пример этого явления. Мы создадим список left и добавить его в другой список outer:

>>> outer = [] 
>>> left = [1, 3] 
>>> outer.append(left) 
>>> outer 
[[1, 3]] 

До сих пор так хорошо: Behaving все, как ожидалось. Но теперь давайте изменим left и добавить его в outer снова:

>>> left[0] = 4 
>>> outer.append(left) 
>>> outer 
[[4, 3], [4, 3]] 

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

Это просто исправить: создать left и right заново на каждой итерации цикла for:

for z in range(len(tree[treecount-1])): 
    left=[0, 0] 
    right=[0, 0] 
    left[0] = tree[treecount-1][z][0] 
    right[0] = tree[treecount-1][z][0] + tree[treecount-1][z][1] 
    left[1] = tree[treecount-1][z][1] + tree[treecount-1][z][0] 
    <and so on> 

В качестве альтернативы, вы можете сделать копии left и right перед добавлением их:

tree[treecount].append(list(left)) 
tree[treecount].append(list(right)) 

Кстати, вы можете существенно упростить свой код, если сможете лучше использовать некоторые из идиом Python. Во-первых, повторение за range(len(something)) часто не является необходимым, особенно если вы собираетесь использовать значения непосредственно в качестве индексов. Итерируйте непосредственно над списком. Во-вторых, вы можете распаковать значение tree[treecount-1] непосредственно в операторе for. Затем вы можете использовать отрицательные индексы для индексации с конца списка, сохраняя при этом необходимость поддерживать treecount. С учетом этих изменений первого прохода, ваш код выглядит следующим образом:

def rational(): 
    tree = [[[1,1]]] 
    while True: 
     tree.append([]) 
     for a, b in tree[-2]: 
      left = [a, b + a] 
      right = [a + b, b] 
      tree[-1].extend([left, right]) 
      yield tree 

Там еще место для улучшения, но это уже гораздо более удобным для чтения, чем исходный код.