英文:

Some Issues in Tree Iteration in Python while the Tree Can be Dynamically Generated on the Fly

问题

I've translated the code portion you provided. Here it is:

我正在编写以下功能。给定两组索引（*_indices_lhs* 和 *_indices_rhs*）的根节点，对于出现在左侧和右侧的索引中的每个索引，它都会创建一个子节点，其中

例如 ik, kn 将有一个子节点，该子节点的 *_indices_lhs* 和 *_indices_rhs* 分别为 i 和 n。例如 ikn，ikn（左右两侧的索引相同），预期的结果是您将有3个子节点 kn，kn；in，in；ik，ik，当然，这3个子节点将分别有2个更多的子节点。为了实现这一点，我使用 while 循环迭代树。我将创建根节点，然后保持已创建子节点的引用队列，然后只要此队列不为空，我将迭代以创建可能会生成节点的更多子节点/节点。当我遍历队列的所有内容并且它为空时，我就知道不会再生成更多的子节点。我为此目的实现的代码在这里：

节点如下所示，子节点在成员函数 generate_further_paths 中创建。我创建了所有可能的子节点组合并将它们添加到 _children 成员变量中。
```python
class Node:
    _parent = None
    _depth = 0
    _indices_lhs = list()
    _indices_rhs = list()
    _children_contractions = list()
    _children = list()

    def __init__(self, indices_lhs: list[str], indices_rhs: list[str], depth: int = 0):
        self._indices_lhs = indices_lhs
        self._indices_rhs = indices_rhs
        self._depth = depth
        print(self)

    def generate_further_paths(self):
        if len(self._indices_lhs) == 0 or len(self._indices_rhs) == 0:
            return

        if len(self._indices_lhs) == 1 and len(self._indices_rhs) == 1 \
            and self._indices_lhs[0] == self._indices_rhs[0]:
            return

        print("D1: ", self._depth, ": ", self._indices_lhs, " | ", self._indices_rhs)
        intersected_indices = []
        for i in self._indices_lhs:
            if i in self._indices_rhs:
                intersected_indices.append(i)

        if len(intersected_indices) == 0:
            return

        print("Intersected indices: ", intersected_indices)
        for ii in intersected_indices:
            child_lhs = copy.deepcopy(self._indices_lhs)
            child_lhs.remove(ii)
            child_rhs = copy.deepcopy(self._indices_rhs)
            child_rhs.remove(ii)
            child = Node(child_lhs, child_rhs, self._depth + 1)
            self._children_contractions.append(ii)
            self._children.append(copy.deepcopy(child))

    def __str__(self):
        return f"Node constructed depth {self._depth}:" + "".join(self._indices_lhs) + " * " + \
            "".join(self._indices_rhs) + ", " + str(len(self._children)) + " children"

    def __repr__(self):
        return '<tree node representation>'

生成树的循环方法如下。我试图确保队列元素是对原始对象的引用：

free_lhs = ["i", "k", "n"]
free_rhs = ["i", "k", "n"]
beginNode = Node(free_lhs, free_rhs, 0)
beginNode.generate_further_paths()
queue = copy.copy(beginNode._children)
while len(queue) != 0:
    nq = list()
    for child in queue:
        child.generate_further_paths()
        nnq = copy.copy(child._children)
        nq += nnq
    queue = nq

我认为有些事情出错了，因为在此循环中，我不断获得更多的元素，某些节点在树中增加了它们的子节点数量。以下是示例输出：

D1:  1 :  ['i', 'k']  |  ['i', 'k']
Intersected indices:  ['i', 'k']
Node constructed depth 2:k * k, 4333 children
Node constructed depth 2:i * i, 4334 children

但是深度为2的节点永远不会被迭代以生成树，但它们的子节点不断被推送回它们的成员变量 _children。我更多地来自C++领域，使用引用，我认为不应该发生这种情况，因此我认为这里有些东西没有被引用捕获。

由于名称绑定到真实对象，我希望这种方法不会成为问题。我迭代每个子节点，用生成的子节点列表覆盖前一个队列。我需要更深入地了解我的代码行为，因为我已经阅读了此帖子和其他一些来源，但我无法完全理解它。

<details>
<summary>英文:</summary>
I am writing the following functionality. A root nodes is given with 2 set of indices (*_indices_lhs* and *_indices_rhs*), and fore every index that apperas in both the left hand side and right hand side it creates a children, where 
For example ik, kn will have one children where the *_indices_lhs* and *_indices_rhs* of the children will be respectively i and n. In the case of for example ikn, ikn (Identical indices on the left and right hand side) the expected outcome is that you would have 3 children kn, kn; in, in; ik, ik and ofc these 3 children would have each 2 more children. To implement this I iterate the tree with a while loop. I would create the root node and then keep a queue of references of created children, and I would then iterate as long as this queue is not empty to create further children/nodes that might create nodes. And when I iterate through all of the queue and when it is empty, then I can know that no more children can be generated. The code I have implemented for this purpose is here:
The node looks as following, children are created in the member function generate_further_paths. I create all the possible children combinations and add them to _children member variable.
```python
class Node:
_parent = None
_depth = 0
_indices_lhs = list()
_indices_rhs = list()
_children_contractions = list()
_children              = list()
def __init__(self, indices_lhs: list[str], indices_rhs: list[str], depth: int = 0):
self._indices_lhs = indices_lhs
self._indices_rhs = indices_rhs
self._depth = depth
print(self)
def generate_further_paths(self):
if len(self._indices_lhs) == 0 or len(self._indices_rhs) == 0:
return
if len(self._indices_lhs) == 1 and len(self._indices_rhs) == 1 \
and self._indices_lhs[0] == self._indices_rhs[0]:
return
print(&quot;D1: &quot;, self._depth, &quot;: &quot;, self._indices_lhs, &quot; | &quot;, self._indices_rhs)
intersected_indices = []
for i in self._indices_lhs:
if i in self._indices_rhs:
intersected_indices.append(i)
if len(intersected_indices) == 0:
return
print(&quot;Intersected indices: &quot;, intersected_indices)
for ii in intersected_indices:
child_lhs = copy.deepcopy(self._indices_lhs)
child_lhs.remove(ii)
child_rhs = copy.deepcopy(self._indices_rhs)
child_rhs.remove(ii)
child = Node(child_lhs, child_rhs, self._depth + 1)
self._children_contractions.append(ii)
self._children.append(copy.deepcopy(child))
def __str__(self):
return f&quot;Node constructed depth {self._depth}:&quot; + &quot;&quot;.join(self._indices_lhs) + &quot; * &quot; + \
&quot;&quot;.join(self._indices_rhs) + &quot;, &quot; + str(len(self._children)) + &quot; children&quot;
def __repr__(self):
return &#39;&lt;tree node representation&gt;&#39;

And the loop-approach to generate the tree is as follows. I am trying to ensure that the queue elements are references to the originals:

free_lhs = ["i", "k", "n"]
free_rhs = ["i", "k", "n"]
beginNode = Node(free_lhs, free_rhs, 0)
beginNode.generate_further_paths()
queue = copy.copy(beginNode._children)
while len(queue) != 0:
    nq = list()
    for child in queue:
        child.generate_further_paths()
        nnq = copy.copy(child._children)
        nq += nnq
    queue = nq

I think there is something I understand that there is something wrong happening as in this loop I constantly get more elements, and some nodes in the tree increasing the number of their children. An example output:

D1:  1 :  ['i', 'k']  |  ['i', 'k']
Intersected indices:  ['i', 'k']
Node constructed depth 2:k * k, 4333 children
Node constructed depth 2:i * i, 4334 children

But nodes constructed at depth 2 are never iterated for the generation, but their children are kept pushing back to their member variable _children. I come more from C++ area, and with references, I think this should not have happened so I think something here does not capture by reference.

Since the names are bound to the real objects, I was expecting this approach to not be a problem. I iterate every children overwrite the previous queue with the list of generated children. I need some further insight on have my code behaves, as I have read through this post. and some other sources but I cant grasp it much.

答案1

得分: 0

I want to post @slothrop's comment as answer as it solves the problem.

self._children = list() creates a class variable which is shared upon every instance of the class. Member variables need to be initialized in the __init__ method of the class.

英文:

I want to post @slothrop's comment as answer as it solves the problem.

self._children = list() creates a class variable which is shared upon every instance of the class. Member variables need to be initialized in the __init__ method of the class.