如何实现链式字典值的扁平化处理？

需要将链式关联的字典值做扁平化处理：每个键对应的列表中，若元素本身是字典的键，则递归将该键的列表内容合并进去；未参与任何链式关联的键需保留原样。

解决方案 #

我们可以分两步实现需求：

1. 识别字典中的根键：即没有被其他任何键的值列表引用的键（这些是最终需要保留的键）
2. 对每个根键递归展开所有链式关联的元素，生成扁平化列表

代码实现 #

首先实现递归展开单个键链式元素的函数：

def flatten_chain(d, key, visited=None):
    # 用visited集合防止循环引用导致无限递归
    if visited is None:
        visited = set()
    if key in visited:
        return []
    visited.add(key)
    flattened = []
    for item in d[key]:
        flattened.append(item)
        # 如果当前元素是字典的键，递归展开它的关联内容
        if item in d:
            flattened.extend(flatten_chain(d, item, visited))
    return flattened

然后实现识别根键并生成最终扁平化字典的函数：

def flatten_dict_chains(original_dict):
    # 找出所有被其他键引用的键（出现在值列表里的字典键）
    referenced_keys = set()
    for values in original_dict.values():
        for val in values:
            if val in original_dict:
                referenced_keys.add(val)
    
    # 根键是未被任何其他键引用的键
    root_keys = [k for k in original_dict if k not in referenced_keys]
    
    # 对每个根键展开链式内容，构建结果字典
    result = {}
    for key in root_keys:
        result[key] = flatten_chain(original_dict, key)
    return result

测试示例 #

示例1 #

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

flattened_a = flatten_dict_chains(a)
print(flattened_a)
# 输出: {'foo': ['bar', 'baz', 'baz2', 'bax']}

示例2 #

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

flattened_a = flatten_dict_chains(a)
print(flattened_a)
# 输出: {'foo': ['bar', 'baz'], 'bar2': ['bax']}

循环引用处理 #

如果字典存在循环链式（比如A引用B，B引用A），函数会自动终止递归，避免无限循环：

a = {}
a["foo"] = ["bar"]
a["bar"] = ["foo"]

flattened_a = flatten_dict_chains(a)
print(flattened_a)
# 输出: {'foo': ['bar']}

内容的提问来源于stack exchange，提问作者maxisme