Построить дерево-иерархию из двумерного списка

Question

У меня есть 2D-список, который выглядит примерно так:

[
    ["elem1","elem2"],
    ["elem1","elem3"],
    ["elem4","elem7"],
...
]

И я хочу создать вложенный словарь, который будет выглядеть примерно так:

[{"elem1":["elem2","elem3"]},{"elem4":"elem7"}]

Так что Чем выше индекс в одном из начальных подсписков, тем выше будет иерархическое положение в сгенерированном дереве. Как бы вы go об этом в python? Как вы называете это «древовидность»? Я чувствую, что должен быть пакет, который делает именно это.

Answer 1

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

Прежде всего, формат вывода в вопросе не может полностью представить дерево: например, данные

[
    ["elem1", "elem2"],
    ["elem1", "elem3"],
    ["elem4", "elem7"],
    ["elem3", "elem5"],
]

... должны быть быть похожим на [{elem1":["elem2","elem3"]},{"elem4":"elem7"}], но добавить elem5 как дочерний элемент elem3, однако elem3 является строковым типом, в котором нет места для хранения дочерних элементов. Таким образом, я предлагаю следующий формат вывода:

{'elem4': {'elem7': {}}, 'elem1': {'elem2': {}, 'elem3': {'elem5': {}}}}

Здесь каждый узел представлен в виде словаря от имен дочерних узлов до значений дочерних узлов, поэтому дерево содержит только root узел выглядит как {}, а дерево с 3 узлами (root + 2 потомка) выглядит как {'child1': {}, 'child2': {}}.

Чтобы по очереди получить список родительско-дочерних ассоциаций и превратить их в такие дерево вы можете использовать этот код:

def treeify(data):
    # result dictionary
    map_list = {}
    # initially all nodes with a child, will have items removed later
    root_nodes = {parent for parent, child in data}

    for parent, child in data:
        # get the dictionary that this node maps to (empty dictionary by default)
        children = map_list.setdefault(parent, {})
        # add this connection
        children[child] = map_list.setdefault(child, {})
        # remove node with a parent from the set of root_nodes
        if child in root_nodes:
            root_nodes.remove(child)

    # return the dictionary with only root nodes at the root
    return dict((root_node, map_list[root_node]) for root_node in root_nodes)

print(treeify([
    ["elem1", "elem2"],
    ["elem1", "elem3"],
    ["elem4", "elem7"],
    ["elem3", "elem5"],
]))

Answer 2

Вот код, который может помочь вам получить в качестве требуемого вывода

data = [
    ["elem1","elem2"],
    ["elem1","elem3"],
    ["elem4","elem7"],
]

maplist = {}
for a in data:
    if a[0] in maplist:
         maplist[a[0]].append(a[1])
    else:
        maplist[a[0]] = [a[1]]

print(maplist)

Чтобы отсортировать по элементу списка, вы можете использовать следующий код

sorted_items = sorted(maplist.items(), key = lambda item : len(item[1]), reverse=True)