在字典列表中查找循环路径 (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 的字典有“send_to_id”= 1，因此“id”= 1 的字典就是我所说的目标层，这两个项目的总和将被聚合与正常情况不同。

不允许的是这样的循环，其中第 1 项指向第 2 项，第 2 项指向第 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

最好的第一步可能是创建仅包含地图的字典。我们可以用一个很好的 dictionary comprehension 来做到这一点（看下面第二个绿色代码示例块）。

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}

现在我们有一个稍微容易解决的问题，我们可以使用 previously made solutions 来帮助我们。具体来说，我们基本上可以重复使用“Update”之后发布的解决方案，并将我们上面的代码添加到其中。

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 []

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

Finding a circular path in a list of dicts (Python)

python

dictionary

list

path

circular-dependency