Pythonでツリーが間違ってビルドされています

Question

data = {'murtaza':('arnav', 'ohjun'), 
     'ohjun':('arnav', 'murtaza'), 
     'arnav':('ohjun', 'murtaza')} 

class node: 
    predecessors=[] 
    nexts=[] 
    student='' 
    def __init__(self, student='', predecessors=[]): 
     self.student=student 
     self.predecessors=predecessors 
    def grow(self, max=6, depth=0): 
     if not self.student in self.predecessors: 
      self.predecessors.append(self.student) 
      for pref in data[self.student]: 
       next=node(pref, self.predecessors) 
       print(depth, self.predecessors, self.student, pref) 
       next.grow(max, depth=depth+1) 
       self.nexts.append(next) 
     else: 
      return 

ここでは、ノードのデータとクラス定義を示します。ノードオブジェクトのgrow()メソッドを呼び出すと、データ内の生徒の名前が検索され、その生徒に関連付けられた名前（つまり、そのプリファレンス、つまりfor pref in data[self.student]）が新しい現在のノードから分岐したノードに追加し、その新しいノードでgrow()を呼び出します。この方法では、生徒がシーケンスに2回出現しない限り、ツリーを構築し続けるので、if not self.student in self.predecessorsをチェックします。

問題は、前任者がツリー内で正しく記憶されていないように見えます。何らかの理由で、兄弟ノードが突然子どもの先祖をすべて取得します。ここでは、プログラムの出力は次のようになります。

0 ['murtaza'] murtaza arnav 
1 ['murtaza', 'arnav'] arnav ohjun 
2 ['murtaza', 'arnav', 'ohjun'] ohjun arnav 
2 ['murtaza', 'arnav', 'ohjun'] ohjun murtaza #as expected up to here 
1 ['murtaza', 'arnav', 'ohjun'] arnav murtaza 
0 ['murtaza', 'arnav', 'ohjun'] murtaza ohjun 

私はそれを読むことを期待：

0 ['murtaza'] murtaza arnav 
1 ['murtaza', 'arnav'] arnav ohjun 
2 ['murtaza', 'arnav', 'ohjun'] ohjun arnav 
2 ['murtaza', 'arnav', 'ohjun'] ohjun murtaza 
1 ['murtaza', 'arnav'] arnav murtaza 
0 ['murtaza'] murtaza ohjun 
1 ['murtaza', 'ohjun'] ohjun arnav 
2 ['murtaza', 'ohjun', 'arnav'] arnav ohjun 
2 ['murtaza', 'ohjun', 'arnav'] arnav murtaza 
1 ['murtaza', 'ohjun'] ohjun murtaza 

は私が間違って書いたコードを理解するアム、またはアルゴリズムの間違ったの私の理解ですか？あるいは私の実装は間違っていますか？私は本当に木を作る方法を理解していると思っていたが、これは私が考えるべき方法では機能していないようだ。

編集：私はこのような本体が見えることを追加する必要があります

mort = node() 
mort.student='murtaza' 
mort.grow() 

Answer 1

このライン：

next=node(pref, self.predecessors) 

をself.predecessorsのコピーを作成しません、代わりにそれは名前のへの参照を渡しますlistオブジェクトです。同様に、この行：

self.predecessors=predecessors 

predecessorsのコピーを作成しません。その結果、すべてのnodeオブジェクトはまったく同じリストで動作します。 1つのオブジェクトが.append()を呼び出すと、すべてのオブジェクトのpredecessorリストが更新されます。

ソリューションはそうのように、copy.deepcopy()でこれらの呼び出しのいずれかを置き換えることです：

self.predecessors = copy.deepcopy(predecessors) 

あなたの正確なデータ構造upongによっては、あなたの代わりにcopy.copy()が必要な場合があります。

また、ご質問とは無関係かもしれませんが、predecessorsのデフォルト値を__init__()に設定しても、期待通りの結果は得られません。 （hereを参照）。代わりにこれを試してみてください：

def __init__(self, student='', predecessors=None): 
    self.student=student 
    if predecessors is None: 
     self.predecessors = [] 
    else: 
     self.predecessors=copy.deepcopy(predecessors)