我可以使用哪种算法来确定导致当前状态的一系列操作？

Question

假设我有一个包含名称（更改）和静态ID的字典，如下所示：

names = {
"A" : "01",
"B" : "02",
"C" : "03",
"D" : "04"
}

我有一本字典，其中包含如下名称更改：

history = [
{"new": "A", "old": "W"},
{"new": "B", "old": "Y"},
{"new": "Y", "old": "X"},
{"new": "C", "old": "S"},
{"new": "D", "old": "C"},
{"new": "C", "old": "F"}
]

底部的更改是按时间顺序最先发生的更改，并且没有两个对象可以同时具有相同的名称

我要做的是用最终名称的静态ID标记这些更改。在上面的变化字典中，它看起来是这样的：

output = {
"01":{"new": "A", "old": "W"},
"02":{"new": "B", "old": "Y"},
"02":{"new": "Y", "old": "X"},
"03":{"new": "C", "old": "S"},
"04":{"new": "D", "old": "C"},
"04":{"new": "C", "old": "F"}
}

这就是我试图设置的内容（不起作用！）：

def solveRecursively(change, names, history):
    new = change["new"]
    old = change["old"]

    hasAnotherNameChange = False
    otherNameChange = None

    for otherChange in history:
        if otherChange.get("old") == new and (not the same change):
            hasAnotherNameChange = True
            otherNameChange = otherChange
    
    if hasAnotherNameChange:
        return handle_name_change(otherNameChange, names, history)
    elif new in names:
        return names[new]
    else:
        return None

output = {}
for change in history:
    ID = solveRecursively(change, names, changes)
    output[ID] = change

它所做的是对每一个更改进行检查，以确定当前名称（新名称）是否位于另一个更改的旧字段中

在以下情况下，它会运行到无限循环中：

history = {
{"new": "A", "old": "X"},
{"new": "X", "old": "A"},
{"new": "A", "old": "X"}
}

我尝试过的每一种方法都会陷入困境。我觉得必须有某种适合这个问题的算法或数据结构。一张图表、一棵树或其他什么，但我完全被难住了

旁注：每个更改都有一个唯一的ID，因此可以避免与同一个对象进行比较，并按相反的时间顺序进行排序（最晚在顶部，最早在底部）

Answer 1

你可以用熊猫来做这件事

首先从history创建一个数据帧，并使用names添加一个新列

import pandas as pd

df = pd.DataFrame(history)

df['key'] = df['new'].map(names)
df['key'] = df['key'].ffill()  # fill NaN value with previous row value

# print(df)

  new old key
0   A   W  01
1   B   Y  02
2   Y   X  02
3   C   S  03
4   D   C  04
5   C   F  03

然后apply()按行调用函数以使用所需格式构造

out = df.apply(lambda row: {row['key']: {'new': row['new'], 'old': row['old']}}, axis=1).tolist()

# from pprint import pprint
# pprint(out)

[{'01': {'new': 'A', 'old': 'W'}},
 {'02': {'new': 'B', 'old': 'Y'}},
 {'02': {'new': 'Y', 'old': 'X'}},
 {'03': {'new': 'C', 'old': 'S'}},
 {'04': {'new': 'D', 'old': 'C'}},
 {'03': {'new': 'C', 'old': 'F'}}]

您想要的输出是一个具有相同键的dict。但是，Python中不允许字典中存在重复键。所以我给你一份口述清单