Создать иерархию из словаря списков

Question

У меня есть словарь списков:

a = { 
     'a': [1, 2, 3], 
     'b': [1, 2, 4], 
     'c': [1, 2], 
     'd': [1, 2, 3, 4, 5], 
     'e': [3], 
     'f': [3, 7], 
     'g': [3, 3], 
     'h': [3, 3, 3, 3, 3], 
     'i': [3, 3, 3, 3, 4], 
    } 

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

  /\ 
      / \ 
      e  c 
      /\  /\ 
      f g a b 
      /\ | 
      h i d 

иерархия выглядит следующим образом: массив g является префиксом массива h и i и, следовательно, является их предком. Но e является префиксом g, так что e является предком g.

Вот моя идея, как достичь этого результата.

• Сортировка словаря на основе количества элементов в списке, который мне удалось достичь с s = sorted(a.items(), key=lambda e: len(e[1])). Это даст мне следующую структуру:

.

('e', [3]) 
('c', [1, 2]) 
('g', [3, 3]) 
('f', [3, 7]) 
('a', [1, 2, 3]) 
('b', [1, 2, 4]) 
('d', [1, 2, 3, 4, 5]) 
('h', [3, 3, 3, 3, 3]) 

• Сейчас я могу найти прародитель перебирая элементы и проверок, если элемент является префиксом других элементов. Начиная с первого. e является префиксом g, f и h. И c является префиксом a, b, d. Итак, эти два элемента - родители.

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

Так же кто-нибудь знает, как подойти к этой проблеме. Или я слишком усложняю ситуацию, и есть более простой способ достичь решения.

P.S. это не задание на домашнее задание или вопрос с интервью (также может быть). Это просто моя абстракция от проблемы, которую я пытаюсь решить.

Answer 1

Другие люди уже дают Methord, я просто пишу код здесь:

Первый сорт:

t = sorted(a.items(), key=lambda x: x[1]) 

Билд структура

ret = {} 

def build(ret, upv): 
    if not t: 
     return (None, None) 
    k, v = t.pop(0) 
    while k and v: 
     if upv and v[:len(upv)] != upv: 
      return (k, v) 
     r = {} 
     ret[k] = r 
     k, v = build(r, v) 
    return None, None 

build(ret, None) 
print ret 

Answer 2

данного объекта, который имеет список детей, а также функцию is_prefix, и ваш отсортированный список объектов, я не понимаю, почему это не будет работать

for indx, potential_prefix in enumerate(your_list): 
    for potential_child in your_list[indx:]: 
     if is_prefix(potential_prefix, potential_child): 
      potential_prefix.add_child(potential_child) 
      # and optionally 
      potential_child.add_parent(potential_prefix) 

Answer 3

Как насчет построения дерева с набор вложенных словарей, так что вы бы получить доступ к e узел по tree[3] и h узел по tree[3][3][3][3][3]:

from collections import nested 

def nested(): 
    return defaultdict(nested) 

def build_tree(data): 
    tree = nested() 
    for name, path in data.items(): 
     d = tree 
     for p in path: 
      d = d[p] 
     d["value"] = name 
    return tree 

Пример вывода:

>>> a = { 
    'a': [1, 2, 3], 
    'b': [1, 2, 4], 
    'c': [1, 2], 
    'd': [1, 2, 3, 4, 5], 
    'e': [3], 
    'f': [3, 7], 
    'g': [3, 3], 
    'h': [3, 3, 3, 3, 3], 
    'i': [3, 3, 3, 3, 4], 
} 

>>> import json # for pretty printing, note that in python the keys are ints, not str 
>>> print(json.dumps(build_tree(a), indent=4)) 
{ 
    "1": { 
     "2": { 
      "3": { 
       "4": { 
        "5": { 
         "value": "d" 
        } 
       }, 
       "value": "a" 
      }, 
      "4": { 
       "value": "b" 
      }, 
      "value": "c" 
     } 
    }, 
    "3": { 
     "7": { 
      "value": "f" 
     }, 
     "3": { 
      "3": { 
       "3": { 
        "3": { 
         "value": "h" 
        }, 
        "4": { 
         "value": "i" 
        } 
       } 
      }, 
      "value": "g" 
     }, 
     "value": "e" 
    } 
} 

Answer 4

Просто сортировки массивов в лексикографическом порядке:

(c,[1,2]), 
(a,[1,2,3]), 
(d,[1,2,3,4,5]), 
(b,[1,2,4]), 
(e,[3]), 
(g,[3,3]), 
(h,[3,3,3,3,3]), 
(i,[3,3,3,3,4]), 
(f,[3,7]) 

Тогда решение довольно очевидно.

root 
Lc 
|La 
||Ld 
|Lb 
Le 
Lg 
|Lh 
|Li 
Lf 

Вам нужно только отслеживать путь формы parent по префиксу. С предыдущей строки. Вы сформируете нечто вроде стека. root имеет пустой набор, поэтому надавите на стек. c имеет (пустой) префикс как корень, поэтому root является родителем c. Нажмите c на стек. a имеет префикс, который равен c сверху стека, поэтому c является родителем a. нажмите a на стеке. d имеет префикс такой же, как a поверх стека, поэтому a является родителем d и нажимаем на стек. b не имеет префикса d поверх стека, поэтому поп. То же самое для a, затем поп. Теперь есть c, который является префиксом, поэтому b имеет родителя c. Нажмите b на стек. И продолжайте так же.

В Erlang просто:

-module(tree_from_prefix). 

-export([tree/1]). 

is_prefix(_, []) -> true; 
is_prefix([H|A], [H|B]) -> is_prefix(A, B); 
is_prefix(_, _) -> false. 

tree(L) -> 
    tree(lists:keysort(2, L), [{root, []}]). 

tree([], _) -> []; 
tree([{X, L} = Record|T] = List, [{Parent, Prefix}|R] = Stack) -> 
    case is_prefix(L, Prefix) of 
    true -> [{Parent, X}|tree(T, [Record|Stack])]; 
    false -> tree(List, R) 
    end. 

И результат

1> tree_from_prefix:tree([{e,[3]},{c,[1, 2]},{g,[3, 3]},{f,[3, 7]},{a,[1, 2, 3]},{b, [1, 2, 4]},{d,[1, 2, 3, 4, 5]},{h,[3, 3, 3, 3, 3]},{i,[3, 3, 3, 3, 4]}]). 
[{root,c}, 
{c,a}, 
{a,d}, 
{c,b}, 
{root,e}, 
{e,g}, 
{g,h}, 
{g,i}, 
{e,f}] 

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