Лучший способ упростить вложенный список Python в структурированное дерево (при сохранении порядка) - PullRequest
Новая
       37

Лучший способ упростить вложенный список Python в структурированное дерево (при сохранении порядка)

2 голосов
/ 22 сентября 2019

Допустим, у меня есть список Python 3.6, который выглядит следующим образом: 

l1 = [
     [a,b,c], 
     [b,c], 
     [c], 
     [d, e], 
     [e]
     ...
]

Мне нужно преобразовать его в древовидную структуру, используя anytree , чтобы он выглядел таккак это: 

>>> print(RenderTree(l1))

l1
|__ a
|   |__b
|      |__c
|___d
    |__e

Считайте, что объекты a, b, c, d, e являются строкой, если это помогает каким-либо образом.В настоящее время я прочитал много документации для anytree и некоторое время искал в StackOverflow, но не смог найти ничего, что помогло бы мне решить эту проблему.Каким самым питоническим способом я могу решить эту проблему?

Редактировать: Чтобы добавить пояснение, исходный список l1 должен представлять дерево, где первый элемент в l1 является родительским узлом, икаждый узел внутри него является дочерним узлом.Каждый дочерний узел может быть дочерним узлом перед ним и т. Д.

Редактировать Редактировать: Итак, вот как выглядит (гипотетически) исходный список: 

l1 = [
['a', 'b', 'c'],
['b', 'c'],
['c'],
['d', 'e'],
['e']
]

Здесьпервый элемент каждого подсписка всегда будет родительским для этой ветви.Соединение каждой из этих веток привело бы к получению нужного мне формата, но я изо всех сил пытался выразить это словами (сейчас 2 часа ночи).Вот некоторые из моих попыток:

Для преобразования списка в узлы: 

from anytree import Node

l = []

for x in l1:
    a = Node(x[0])
    for i in x[1:]:
        Node(i, parent = a)
    l.append(a)

Однако это возвращает дерево / список так: 


>>> l
[Node('/a'), Node('/b'), Node('/c'), Node('/d'), Node('/e')]
>>> print(RenderTree(l[0]))
Node('/a')
├── Node('/a/b')
└── Node('/a/c')
>>> print(RenderTree(l[1]))
Node('/b')
└── Node('/b/c')
>>> print(RenderTree(l[2]))
Node('/c')
>>> print(RenderTree(l[3]))
Node('/d')
└── Node('/d/e')
>>> print(RenderTree(l[4]))
Node('/e')

Для фильтрацииВ этом случае я попытался сделать следующее: 

def tuple_replace(tup, pos, val):
    return tup[:pos] + (val,) + tup[pos+1:]

>>> l2=[]
>>> for pos, x in enumerate(l):
    for pos_2, i in enumerate(x.children):
        for j in l[pos+1:]:
            if j.name == i.name:
                x.children = tuple_replace(x.children, pos_2, i)
                break
        l2.append(x)

>>> for x in l2:
    print(RenderTree(x))


Node('/a')
├── Node('/a/b')
└── Node('/a/c')
Node('/a')
├── Node('/a/b')
└── Node('/a/c')
Node('/b')
└── Node('/b/c')
Node('/d')
└── Node('/d/e')

Это шаг, на котором я сейчас нахожусь

Редактировать Редактировать редактировать:

Итак, путь дереваПредставлено, что у меня есть функция, которая возвращает список вроде l1, и имеет следующую логику:

Каждый элемент в списке состоит из 2 частей.Родитель и дети.Родитель является первым элементом в списке, а все остальное - это его дети, или это дети детей и так далее.Таким образом, такие элементы, как: [a, b, c] и [d, e, f, g] представляют все элементы в ветви, а не только непосредственные родители, которые продолжают падать.Вот где остальные элементы вступают в игру.Следующий элемент обычно содержит первый дочерний элемент родителя: [b, c] и [e, f] и [g].Но теперь элемент [d, e, f, g] отличается от [a, b, c], потому что внутри него есть две разные ветви, а не одна.Таким образом, дерево, такое как это: 

l1
|
|_a
|   |__b
|   |__c
|
|_d
   |__e
   |    |__f
   |__g

Будет описываться как:

Редактировать: исправлено дерево ввода, потому что f не имеет отдельной ветви 

l1=[
 [a,b,c],
 [b, c],
 [c],
 [d,e,f,g],
 [e,f]
 [f]
 [g]
]

1 Ответ

1 голос
/ 22 сентября 2019

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

from functools import reduce
data = [['a', 'b', 'c'], ['b', 'c'], ['c'], ['d', 'e'], ['e']]
new_data = [a for i, a in enumerate(data) if all(a[0] not in c for c in data[:i])]
def to_tree(d):
   return d[0] if len(d) == 1 else {d[0]:to_tree(d[1:])}

tree = reduce(lambda x, y:{**x, **y}, [to_tree(i) for i in new_data])

Теперь, чтобы напечатать структуру: 

import re
def print_tree(d, c = 0):
   for a, b in d.items():
     yield f'{"|" if c else ""}{"   "*c}|__{a}'
     if not isinstance(b, dict):
        yield f'{"|" if (c+1) else ""}{"   "*(c+1)}|__{b}'
     else:
        yield from print_tree(b, c+1)

*r, _r = print_tree(tree)
print('l1\n{}\n{}'.format('\n'.join(r), re.sub("^\|", "", _r)))

Вывод: 

l1
|__a
|  |__b
|     |__c
|__d
   |__e

Редактировать: необязательный подход к формированию дерева:

Текущий метод to_tree предполагает, что структура родительско-дочерних узлов будет включена какодин список для каждого родительского узла, т.е. ['a', 'b', 'c'] - это полный путь к дереву, а ['d', 'e'] - также полный путь.Если возможно, что это не относится к будущим входам, вы можете использовать приведенный ниже код для создания словарей: 

def to_tree(d, s, seen = []):
   _l = [b for a, b, *_ in d if a == s and b not in seen]
   return s if not _l else {s:to_tree(d, _l[0], seen+[s, _l[0]])}

data = [['a', 'b', 'c'], ['b', 'c'], ['c'], ['d', 'e'], ['e']]
p = [a[0] for i, a in enumerate(data) if all(a[0] not in c for c in data[:i])]
c = [i for i in data if len(i) > 1]
tree = reduce(lambda x, y:{**x, **y}, [to_tree(c, i) for i in p])
...