分支排序列表

Question

我有一个树网络，我想在其中找到所有父节点的 'generation'（见下文）。

所有父节点恰好有两个子节点。

这在列表中显示为：

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

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

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)

Answer 2

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

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

然后，如果您将 forestas 构造成一个嵌套字典，则很容易获得父节点世代的列表。

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]

显然，这需要做更多的工作，但根据您正在做的事情，这可能是值得的。请注意，由于字典和结构不同，顺序并不完全相同。

分支排序列表

list of branches sorting

python

tree

list-comprehension

list