python - 分支排序列表

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:您提供的父子数组定义缺少一些逗号。

更新

这是性能版本，具有内存递归:

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)