递归函数：将嵌套列表转换为嵌套字典

Question

我有一个列表的列表，我想得到一个字典的字典：

import json

list = [
        ['1', '2', '3'],
        ['a', 'b'],
        ['I', 'II'],
        ['A', 'B', 'C'],
        ['A', 'B', 'D']
    ]

dict = {}  
    
for val in list:
    count = len(val)
    if val[0] not in dict:
        dict[val[0]] = {}
    if count == 3:
        if val[1] not in dict[val[0]]:
            dict[val[0]][val[1]] = {}
        if val[2] not in dict[val[0]][val[1]]:
            dict[val[0]][val[1]][val[2]] = ''
    else:
        if val[1] not in dict[val[0]]:
            dict[val[0]][val[1]] = ''
            
print (json.dumps(dict, sort_keys=True, indent=4))

输出：

{
    "1": {
        "2": {
            "3": ""
        }
    },
    "A": {
        "B": {
            "C": "",
            "D": ""
        }
    },
    "I": {
        "II": ""
    },
    "a": {
        "b": ""
    }
}

这个方法适用于列表中只有两个或三个元素，但是如果列表中有更多（随机）元素，就必须使用一种递归函数，现在我无法想到。

- RichMC

---

“我必须要有一种递归函数” - 为什么？这是一个练习要求吗？另外，请停止使用像list和dict这样的内置名称作为变量名。 - Tomerikoo

列表中可能有10个、20个元素……所以我需要一个函数。 - RichMC

你的数据是否可以包含以相同元素开头但长度不同的列表，例如 ['A', 'B'], ['A', 'B', 'D']？ - Hans

Answer 1

这里没有必要使用递归函数（除非有要求）。同时，您也不需要考虑列表的大小或数量。只需在遍历每个列表时，保持更新内部字典的引用即可。

您还可以使用setdefault来避免检查是否已经存在相应的键。

d = {}
for sub in l:
    inner = d
    for elem in sub[:-1]:
        inner = inner.setdefault(elem, {})
        
    inner[sub[-1]] = ""

如果出于某种原因您真的想要将此作为递归函数，那么以下是一个等效版本。它从基本字典开始，在每次调用时创建内部字典，并且下一次调用会向下一个字典级别并传递剩余的列表。 基本情况是当列表只有一个元素时，使用字符串而不是字典。 为了简化起见，使用了 `setdefault`：

def create_dict(l, d):
    if len(l) == 1:
        d[l[0]] = ""
    else:
        d = d.setdefault(l[0], {})
        create_dict(l[1:], d)

d = {}
for sub in l:
    create_dict(sub, d)

---

^{尽量避免使用内置的变量名。 list 和 dict 都代表了对应类的构造函数，在程序中不再可用。}

- Tomerikoo

Answer 2

我写了一个基本的逻辑递归函数。我已经测试过你提供的示例输入，它可以正常工作。

def subdict(dic,val):
    if len(val)==1:
        dic.update({val[0]:""})
    else:
        if val[0] not in dic.keys():
            dic.update({val[0]:{}})
        subdict(dic[val[0]],val[1:])

完全执行：

lists = [
        ['1', '2', '3'],
        ['a', 'b'],
        ['I', 'II'],
        ['A', 'B', 'C'],
        ['A', 'B', 'D']
    ]

rootdict = {}

def subdict(dic,val):
    if len(val)==1:
        dic.update({val[0]:""})
    else:
        if val[0] not in dic.keys():
            dic.update({val[0]:{}})
        subdict(dic[val[0]],val[1:])


for li in lists:
    subdict(rootdict,li)

print(rootdict)

输出：

{'1': {'2': {'3': ''}}, 'a': {'b': ''}, 'I': {'II': ''}, 'A': {'B': {'C': '', 'D': ''}}}

说明： subdict函数：

• 检查是否到达了最后一层，如果是，则通过添加键值对''来终止递归的这个叶子节点。
• 如果我们没有到达最后一层，它会检查key[0]是否不存在于当前字典级别中，如果不存在，则添加该键。然后最后递归进行下一次迭代，进一步深入。

我知道这个逻辑很无聊，但它确实有效 :)

- Rishabh Kumar

---

是的，最终得到了正确的递归答案！请注意，您的elif和else块包含相同的最后一行。如果您测试val[0] not in dic.keys()以执行dic.update({val[0]:{}})，然后无条件地执行subdict(dic[val[0]],val[1:])，那么您的解决方案将更加简洁，我认为也更易于理解。逻辑是：1）如果尚未存在这样的键，则添加具有空字典的键，然后2）无条件添加新元素。 - CryptoFool

@CryptoFool，你的观察是正确的。但我不能无条件地保留subdict(dic[val[0]],val[1:])这一行。请记住，在if len(val)==1:检查中没有这一行！代码仍然可以进行优化，我会尽快审查。 - Rishabh Kumar

@CryptoFool请检查，我已经对我的帖子进行了编辑。 - Rishabh Kumar

Answer 3

如Tomerikoo所说，你不必使用递归，但如果你想用递归解决它，你应该定义一个递归函数，以你的“基本情况”——列表中的最后一个元素作为参数。

然后迭代你的输入（列表的列表），并将“当前工作列表”传递给递归函数。

更新：由于Tomerikoo发现了一个错误，我不得不修复我的答案。当你使用字典的.update()方法时，它不会对值进行“深拷贝”。因此，你必须自己实现它，使用另一个递归函数。

你需要实现一个merge_dict函数，在更新结果之前。下面的函数接受两个字典，并使用深拷贝将它们合并。我将尝试简化步骤：

1. 迭代第二个字典项，如果“值”是一个字典，则 - 2. 检查“键”是否已经存在于结果中，如果不存在，则创建一个空字典，并再次调用合并函数 3. 如果值不是字典-只需将其添加到结果字典中。

---

import json
from copy import deepcopy

final_dict = {}
my_list = [
    ['1', '2', '3'],
    ['a', 'b'],
    ['I', 'II'],
    ['A', 'B', 'C'],
    ['A', 'B', 'D']
]


def nested_dict(a_list):
    if len(a_list) == 1:
        print("base case: {}".format(a_list))
        return {a_list[0]: ""}

    return {a_list[0]: nested_dict(a_list[1:])}


def merge_dicts(d1, d2):
    res = deepcopy(d1)

    for k, v in d2.items():
        if isinstance(v, dict):
            res[k] = merge_dicts(res.get(k, {}), v)
        else:
            res[k] = v

    return res


for sub in my_list:
    my_dict = nested_dict(sub)
    final_dict = merge_dicts(final_dict, my_dict)


print("final dict: {}".format((json.dumps(final_dict, sort_keys=True, indent=4))))

- Chen A.

---

是的，根据@Tomerikoo的说法，你将每个列表单独转换为字典结构，而不考虑已经存在的内容，这意味着你的代码无法正确处理任何以共同元素开头的列表。相反，每当出现这种情况时，你处理的每个后续列表都会覆盖任何以相同元素开头的先前列表的贡献。 - CryptoFool

@CryptoFool 谢谢你指出来，我已经相应地更新了我的答案。 - Chen A.