分支排序列表

Question

我有一个树网络，我想在其中找到所有父节点的“生成”（见下文）。你知道吗

所有父节点正好有两个子节点。你知道吗

这在列表中显示为：

parents  = [   2,     3,           1,       5,        4,          7,          8,          9,         6,        10     ]
children = [ [4,5],  [0,11],     [6,10]   [1,7]     [8,9]      [12,13],    [14,15],    [16,17],   [18,19],   [20,21]  ]

例如，父节点“2”有直接的子节点[4,5]。你知道吗

我将父节点的生成定义为到没有子节点的节点的最长路径。因此，例如，对于父节点“2”，到没有子节点的节点有许多不同的路由

1）2-->；4-->；9-->；17

2）2-->；5-->；1-->；10-->；21

因为第二个路由是较长的路由，所以父级“2”的生成是4，因为需要4个节点才能到达“21”，而“21”是叶节点。你知道吗

所以在这种情况下，使用parents列表，我想要的结果是：

generation = [4, 1, 2, 3, 2, 1, 1, 1, 1, 1]

其中generation列表的每个索引对应于parents列表中节点的生成。你知道吗

如何从parents和children列表中获取生成列表？你知道吗

Answer 1

虽然有一个简洁的解决方案可以计算每个节点的生成，但您也可以实现跟踪每个节点生成的树数据结构。你知道吗

class Forest:
    def __init__(self, forest_dict):
        self.trees = [Tree(value, children) for value, children in forest_dict.items()]

    def __iter__(self):
        for tree in self.trees:
            for node in iter(tree):
                yield node

class Tree:
    def __init__(self, value, children):
        self.root = node = Node(value)
        self.__recurse(node, children)

    def __recurse(self, node, children):
        for value, subchildren in children.items():
            child = Node(value, node)
            node.addChild(child)
            self.__recurse(child, subchildren)

    def __iter__(self):
        for node in iter(self.root):
            yield node

class Node:
    def __init__(self, value, parent=None):
        self.value = value
        self.parent = parent
        self.children = []
        self.generation = 0

    def addChild(self, child):
        if not self.children:
            node, generation = self, 1
            while node is not None:
                node.generation = max(node.generation, generation)
                generation += 1
                node = node.parent

        self.children.append(child)

    def __iter__(self):
        yield self
        for child in self.children:
            for subchild in iter(child):
                yield subchild

然后，如果将forest结构为嵌套字典，则很容易获得父节点代的列表。你知道吗

forest_dict =   {2: 
                    {4: 
                        {8: 
                            {14: {}, 
                             15: {}
                            }, 
                         9: {16: {}, 
                             17: {}
                            }
                        }, 
                     5: 
                        {1: 
                            {6: 
                                {18: {}, 
                                 19: {}
                                }, 
                            10: 
                                {20: {}, 
                                 21: {}
                                }
                            },
                         7:
                            {12: {},
                             13: {}
                            }
                        }
                    },
                3: 
                    {0: {},
                     11: {}
                    }
                }

forest = Forest(forest_dict)
print [node.generation for node in forest if node.generation]
# [4, 2, 1, 1, 3, 2, 1, 1, 1, 1]

很明显，这是一个更多的工作，但可能是值得的，这取决于你在做什么。注意，由于字典和不同的结构，顺序并不完全相同。你知道吗

Answer 2

这是一个单线解决方案，但性能不太好：

parents  = [   2,     3,           1,       5,        4,          7,          8,          9,         6,        10     ]
children = [ [4,5],  [0,11],     [6,10],  [1,7],    [8,9],     [12,13],    [14,15],    [16,17],   [18,19],   [20,21]  ]

generation=[(lambda f,*x:f(f,*x))(lambda g,i,c:max(g(g,j,c)+1for j in c[i])if i in c else 0,i,dict(zip(parents,children)))for i in parents]

print(generation)

PS:您提供的父数组和子数组定义缺少一些逗号。你知道吗

更新

以下是性能版本，以记忆递归为特征：

parents  = [   2,     3,           1,       5,        4,          7,          8,          9,         6,        10     ]
children = [ [4,5],  [0,11],     [6,10],  [1,7],    [8,9],     [12,13],    [14,15],    [16,17],   [18,19],   [20,21]  ]

generation=(lambda c:list(map((lambda f,m={}:lambda x:m[x]if x in m else m.setdefault(x,f(f,x)))(lambda g,i:max(g(g,j)+1for j in c[i])if i in c else 0),parents)))(dict(zip(parents,children)))

print(generation)