在字典列表中查找一个循环路径(Python)

Question

我有这样的数据

mydict = [
{"id": 0, "item_total": 10000, "send_to_id": None},
{"id": 1, "item_total": 15000, "send_to_id": None},
{"id": 2, "item_total": 30000, "send_to_id": 1},
{"id": 3, "item_total": 20000, "send_to_id": None},
...
]

，其中id总是字典在列表中的位置。

item_totals将被聚合，send_to_id将被聚合。键影响聚合发生的方式。在这里，作为带有"id"的字典。= 2 has "send_to_id"= 1，具有"id"= 1就是我所说的目标层，这两项的总和将以不同于正常的方式聚合。

不允许的是这样的循环，item 1指向item 2, item 2指向item 1。

mydict = [
{"id": 0, "item_total": 10000, "send_to_id": None},
{"id": 1, "item_total": 15000, "send_to_id": 2},
{"id": 2, "item_total": 30000, "send_to_id": 1},
{"id": 3, "item_total": 20000, "send_to_id": None}
]

或者这个，它仍然是圆形的，并且要走三步

mydict = [
{"id": 0, "item_total": 10000, "send_to_id": None},
{"id": 1, "item_total": 15000, "send_to_id": 3},
{"id": 2, "item_total": 30000, "send_to_id": 1},
{"id": 3, "item_total": 20000, "send_to_id": 2}
]

项也不能指向自身。

我不知道该怎么做，但我想接受上面的字典列表，并找出是否存在循环路径，以便我可以向用户提供适当的错误消息。有人能帮忙吗?我正想办法顺着一条路走到下一项，但我脑子里老是打结。

如果重要的话，列表的最大长度将在50左右。

谢谢!

Answer 1

好的第一步可能是创建一个仅包含地图的字典。我们可以通过一个很好的字典理解来做到这一点(看下面第二个绿色代码示例块)。

def get_direct_mappings(data: list) -> dict: 
return {d["id"]: d["send_to_id"] for d in data if d["send_to_id"] is not None} 

现在我们有一个稍微容易解决的问题，我们可以使用以前的解决方案来帮助我们。具体来说，我们基本上可以重复使用&;更新之后发布的解决方案"，并将上述代码添加到其中。

def find_cycles(original_data: list) -> list:
n = {d["id"]: d["send_to_id"] for d in original_data if d["send_to_id"] is not None}
cycles = []
while n:
visited = {}
count = 0
k, v = n.popitem()
while v is not None:
# visited[k] = (count, v)
visited[k] = count
count += 1
k = v
v = n.pop(k, None)
if k in visited:
if len(visited) == 1:
cycle = tuple(visited.keys())
else:
cycle_start = visited[k]
cycle = sorted((c, k) for k, c in visited.items() if c >= cycle_start)
cycle = tuple(k for c, k in cycle)
k = min(range(len(cycle)), key=lambda x: cycle[x])
cycle = cycle[k:] + cycle[:k]
cycles.append(cycle)
return cycles

虽然它不是最漂亮的，但它是有效的。

mydict = [
{"id": 0, "item_total": 10000, "send_to_id": None},
{"id": 1, "item_total": 15000, "send_to_id": 3},
{"id": 2, "item_total": 30000, "send_to_id": 1},
{"id": 3, "item_total": 20000, "send_to_id": 2}
]
print(find_cycles(mydict))
# prints [(1, 3, 2)]
mydict = [
{"id": 0, "item_total": 10000, "send_to_id": None},
{"id": 1, "item_total": 15000, "send_to_id": 2},
{"id": 2, "item_total": 30000, "send_to_id": 1},
{"id": 3, "item_total": 20000, "send_to_id": None}
]
print(find_cycles(mydict))
# prints [(1, 2)]
mydict = [
{"id": 0, "item_total": 10000, "send_to_id": None},
{"id": 1, "item_total": 15000, "send_to_id": None},
{"id": 2, "item_total": 30000, "send_to_id": 1},
{"id": 3, "item_total": 20000, "send_to_id": None},
]
print(find_cycles(mydict))
# prints []