扁平化链接的字典值

我该怎么做呢:

a = {}
a["foo"] = ["bar"]
a["bar"] = ["baz", "baz2"]
a["baz"] = ["bax"]

使a["foo"] = ["bar", "baz", "baz2", "bax"].

另一个例子:

a = {}
a["foo"] = ["bar"]
a["bar"] = ["baz"]
a["bar2"] = ["bax"]

输出:a["foo"] = ["bar", "baz"]和a["bar2"] = ["bax"]

注意bar2索引仍然在那里，因为它没有被合并/扁平。

一个简单的递归函数可以为您解决这个问题:

a = {}
a["foo"] = ["bar"]
a["bar"] = ["baz", "baz2"]
a["baz"] = ["bax"]
def flatten(dic,arg):
if dic.get(arg,[]) == []:
return []
lst = []
for item in dic[arg]:
lst += flatten(dic,item) + [item]
return lst 
print(flatten(a,'foo'))
>> ['bax', 'baz', 'baz2', 'bar']

dic参数定义了你正在使用的字典，arg是字典的键。该函数尝试在字典中为每个ite找到一个新条目作为键。该算法执行像树一样的遍历到根，并在离开每个根时添加项。这也被称为后序走路。然后，您可以对字典中的每个条目执行此操作，以平铺所有键。

注意，我没有考虑顺序。您可以使用另一种遍历树的方法，来更改项目添加到列表中的顺序。

为了完成答案，我把它应用到第二个例子中。我创建了一个新字典，通过:

a = {i:flatten(a,i) for i in a.keys()}

因此，完整的代码将是:

a = {}
a["foo"] = ["bar"]
a["bar"] = ["baz"]
a["bar2"] = ["bax"]
def flatten(dic,arg):
if dic.get(arg,[]) == []:
return []
lst = []
for item in dic[arg]:
lst += flatten(dic,item) + [item]
return lst 
a = {i:flatten(a,i) for i in a.keys()}
>> {'foo': ['baz', 'bar'], 'bar': ['baz'], 'bar2': ['bax']}

注意:正如在注释中所指出的，当您使用:

时，此实现不起作用。

键值对，其中键包含在值
两个键值对，键1包含在值2中，键2包含在值1中这两种情况形成了一个永远不会结束的循环。要解决第一个场景，请确保对于每个键值对，该键不包含在该值中。

# Scenario 1
a['foo'] = ['foo', 'bar']
a['bar'] = ['baz']

应该类似于*:

a['foo'] = a['foo'] - ['foo']

第二个场景有点棘手。对于键1和键2,flatten函数的结果是相同的。最终，这将意味着为其中一个键调用flatten函数，并将两个键从它们的组合值中删除，这样就可以工作了:

# Scenario 2
a['foo'] = ['bar','baz']
a['bar'] = ['foo','bax']

因此应该是类似于*:

的东西

a['foo'] = a['bar'] = a['foo'] + f['bar'] - ['foo','bar']

然而，我认为实现本身以及如何解决不同(更长，更复杂)周期的问题超出了问题的范围。

*:减号运算符在这样的列表上不起作用，但我敢打赌，如果你打算研究这个，你可以想出一个解决方案。

注意:您在评论中提到您不希望'bar'作为您的扁平字典的键。您将需要找到字典的根，以便任何子节点都不是键。为了做到这一点，您需要检查每个键，如果它不在相同或其他键的值中。下面的代码应该可以达到这个目的:

allValues = []
for item in a.values():
allValues += item
roots = {key:a[key] for key in a.keys() if key not in allValues}
>> {'foo': ['baz', 'bar'], 'bar2': ['bax']}

首先，它组合键的所有值。然后，它将通过查看哪个键没有出现在所有值的列表中来创建字典。字典roots为您提供所需的字典。

我想提供一种利用反向查找的解决方案，因为这通常是一种效果良好的策略。为了更清晰，我已经重命名了这些变量。

single_parent = {
"a": ["b"],
"b": ["c", "d"],
"c": ["e"],
}
multiple_parent = {
"a": ["b"],
"b": ["c"],
"d": ["e"],
}

def urparent(reverse: dict, start: str) -> str:
if start in reverse:
return urparent(reverse, reverse.get(start))
return start

def flatten_refs(dx: dict) -> dict:
reverse = dict()
for key, refs in dx.items():
for ref in refs:
reverse[ref] = key
forward = dict()
for key, parent in reverse.items():
apex = urparent(reverse, parent)
current = forward.get(apex, [])
current.append(key)
forward[apex] = current
return forward

print(flatten_refs(single_parent))
print(flatten_refs(multiple_parent))

输出:

{'a': ['b', 'c', 'd', 'e']}  # single_parent
{'a': ['b', 'c'], 'd': ['e']}  # multiple_parent

本质上，您访问每个列表的每个元素并创建一个"反向查找"字典，其中元素指向它的父元素。然后，对于该反向查找中的每个元素，跟踪到父级。最坏情况是O(n^2)，但是您可以很容易地优化urparent()来缓存结果。此外，可以修改该函数以确保循环不会导致问题。(在这种情况下，你的算法应该做什么是不清楚的-也许父项是循环前的最后一项，也许它把它扔出去，也许是别的什么?)

这似乎可以工作:

a = {}
a["bax"] = ["test"]
a["foo"] = ["bar"]
a["bar"] = ["baz", "baz2"]
a["baz"] = ["bax"]
a["aaa"] = ["bbb"]
a["ccc"] = ["ddd", "aaa", "eee"]
a["123"] = ["456"]
vals = list(a.values())
flag = True
while flag:
flag = False
for v in vals:
for st in v:
if st in a:
flag = True
v += a[st]
a.pop(st)
a
# Out[103]: 
# {'foo': ['bar', 'baz', 'baz2', 'bax', 'test'],
#  'ccc': ['ddd', 'aaa', 'eee', 'bbb'],
#  '123': ['456']}

相关内容

最新更新

热门标签：