分支分類列表

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

這裏是一個單行的解決方案，不要太高性能的，但：

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：您所提供的父母和子女數組的定義是缺少某些逗號。

UPDATE

這裏是高性能版本，其特點爲memoized遞歸：

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 

然後，如果您將森林構建爲嵌套字典，則很容易得到父節點代的列表。

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] 

很明顯，這是更多的工作，但可能值得它取決於你在做什麼。請注意，由於詞典和不同的結構，順序不完全相同。