python - 如何从邻接列表递归生成父子字符串列表？

Question

摘要:

我正在尝试创建一个递归函数，从邻接列表中获取数据并将其转换为点表示法。

详细信息:

我将此数据作为元组列表(Python)。数据按id排序，但这是唯一的限制。没有限制父级必须列在子级之前:例如，项目 #3 的父级可以是项目 #7。代数也没有(计划的)限制。

id     name     parent  |  data = [
1      A        0       |          (1, 'A', 0),
2      B        1       |          (2, 'B', 1),
3      C        1       |          ...
4      D        2       |
5      E        2       |
6      F        3       |
7      G        2       |
8      H        6       |          ...
9      I        4       |          (9, 'I', 4)]

我想返回父子点表示法的字符串列表:

A
A.B
A.B.D
A.B.D.I
A.B.E
A.B.G
A.C
A.C.F
A.C.F.H

请注意，每个名称都会显示 - 我发现的其他算法只会返回没有子项的项目。

我尝试过的事情:

Python 代码:

这是我到目前为止所得到的，基于 USF 的数据结构可视化 here .

if len(cat_list) == 0:
    return

for item in cat_list:
    parent_id = item[0]
    name = item[1]
    children = [_x for _x in cat_list if _x[2] == parent_id]

    if len(children) == 0:
        # then we're at the end
        return name
    else:
        sub_problem = cat_list[1:]
        sub_solution = create_categories(sub_problem)
        solution = "{}.{}".format(name, sub_solution)
        print(solution)
        return solution

但是这一切所做的只是获取一个项目并将其一路构建回来:

D.E
C.D.E
B.C.D.E
A.B.C.D.E

SQL:

如果数据存储在 SQLite 数据库中，并且可以使用以下 SQL 获取部分数据:

SELECT
    t1.name AS level1,
    t2.name as level2,
    t3.name as level3,
    t4.name as level4
FROM category AS t1
    LEFT JOIN category AS t2 ON t2.parent = t1.id
    LEFT JOIN category AS t3 ON t3.parent = t2.id
    LEFT JOIN category AS t4 ON t4.parent = t3.id
WHERE t1.name = 'A'

但这有多个问题:

1. 无法扩展到任意深度
2. 不返回中间深度

由于这些限制，我决定用 Python 实现代码。

研究

我查看了很多不同的问题和网站，但没有一个给我“ Eureka ”时刻，因此我在这里问。

This question非常相似，但在 vb.net 中，我对此一无所知。它也没有告诉我如何执行串联。

This question也很相似，但我又不懂语言。看起来 Lookup 函数可能与 python 字典非常相似...

Answer 1

数据准备步骤有点可怕，因为您的 ID 是从 1 开始的，我们需要在位置 0 处有一个阻止元素 None:

original = [(1, 'A', 0),
            (2, 'B', 1),
            (3, 'C', 1),
            (4, 'D', 2),
            (5, 'E', 2),
            (6, 'F', 3),
            (7, 'G', 2),
            (8, 'H', 6),
            (9, 'I', 4)]
ids,data,parents = zip(*original)
data =[None]+list(data)
parents = [None]+list(parents)

一旦您获得正确格式的输入数据，此代码就会起作用:

ids = range(1,10)
parents = [None,0,1,1,2,2,3,2,6,4]
data =[None,"A","B","C","D","E","F","G","H","I"]

def get_parents(node):
    if not parents[node]:
        return data[node]
    return get_parents(parents[node])+data[node]
for id in ids:
    print ".".join(list(get_parents(id)))
>>> 
A
A.B
A.C
A.B.D
A.B.E
A.C.F
A.B.G
A.C.F.H
A.B.D.I