Как рекурсивно создать список родительско-дочерних строк из списка смежности?

Резюме:

Я пытаюсь создать рекурсивную функцию, которая берет данные из списка смежности и преобразует их в точечную запись.

Подробности:

У меня есть эти данные в виде списка кортежей (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 здесь.

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'

Но это имеет несколько проблем:

не масштабируется до произвольной глубины
не возвращает промежуточные глубины

Из-за этих ограничений я решил реализовать код на Python.

Исследовать

Я просмотрел кучу разных вопросов и веб-сайтов, но ни один из них не дал мне момент «Эврика», поэтому я спрашиваю здесь.

Этот вопрос очень похож, но находится в vb.net, о котором я ничего не знаю. Это также не информирует меня о том, как выполнить конкатенацию.

Этот вопрос тоже очень похож, но опять же я не знаю языка. Похоже, что функция Lookup может быть очень похожа на python dict...

python recursion adjacency-list

dthor 02.06.2015 источник

Ответы (2)

arrow_upward
1
arrow_downward

Шаг подготовки данных немного отвратительный, потому что ваши идентификаторы начинаются с единицы, нам нужен блокирующий элемент None в позиции 0:

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

Sebastian Wozny 02.06.2015

arrow_upward
0
arrow_downward

После записи каждого шага на листе бумаги я смог придумать следующее:

def generate_category_strings(cat_list, parent_item, sent_str, retlist=[]):
    """
    Concatenates categories together and returns a list of them.
    """
    if parent_item is None:
        parent_item = cat_list[0]
        retlist.append(parent_item[1])

    parent_id = parent_item[0]
    parent_name = parent_item[1]

    if sent_str is None:
        sent_str = parent_name

    children = [_x for _x in cat_list if _x[2] == parent_id]

    if len(children) == 0:
        # base case, no children
        return ["{}.{}".format(sent_str, parent_name)]
    else:
        for child in children:
            str_to_send = "{}.{}".format(sent_str, child[1])
            retlist.append(str_to_send)
            generate_category_strings(cat_list, child, str_to_send, retlist)
        return retlist

Выполнение этого на исходном наборе данных:

data = [(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),
       ]

a = generate_category_strings(data, None, None)
for item in a:
    print(item)

печатает:

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

dthor 02.06.2015

comment

ты проверил мой ответ? Порядок имеет решающее значение? - Sebastian Wozny; 03.06.2015