python - 通过合并匹配键和键值对来折叠字典

Question

所以我试图找到一种方法来“合并”一个依赖列表，它在 python 中以字典的形式出现，但我一直没能想出一个解决方案。所以想象一个沿着这条线的图:(在这个有向图中所有的线都是向下的箭头)

1   2   4
 \ /   / \
  3   5   8
   \ / \   \
    6   7   9

此图将生成如下所示的依赖项字典:

{3:[1,2], 5:[4], 6:[3,5], 7:[5], 8:[4], 9:[8], 1:[], 2:[], 4:[]}

使得键是图中的节点，它们的值是它们所依赖的节点。我试图将其转换为一棵树的总祖先列表，以便每个节点都是一个键，它的值是指向它的所有节点的列表，而不仅仅是它的直接父节点。生成的字典将是:

{3:[1,2], 5:[4], 6:[3, 5, 1, 2, 4], 7:[5, 4], 8:[4], 9:[8, 4], 1:[], 2:[], 3:[]}

关于如何解决这个问题有什么建议吗？我已经投入了一段时间，尝试了一个我无法开始工作的递归解决方案。

Answer 1

您可以将链式 dict comprehension 与 list comprehension 一起用于最多两个节点。

>>> {k: v + [item for i in v for item in d.get(i, [])] for k,v in d.items()}

{3: [1, 2],
 5: [4],
 6: [3, 5, 1, 2, 4],
 7: [5, 4],
 8: [4],
 9: [8, 4],
 1: [],
 2: [],
 4: []}

---

对于无限深度，可以使用递归方法

def get_ant(node, d):
    if node:
        return d.get(node,[]) + [item for x in d.get(node, []) for item in get_ant(x, d) ]
    return []

然后，

>>> get_ant(6, d)
[3, 5, 1, 2, 10, 4]

获取所有案例:

>>> {k: get_ant(k, d) for k in d.keys()}

{3: [1, 2, 10],
 5: [4],
 6: [3, 5, 1, 2, 10, 4],
 7: [5, 4],
 8: [4],
 9: [8, 4],
 1: [10],
 2: [],
 4: []}