Creare una gerarchia da un dizionario di liste

Question

Ho un dizionario di liste:

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 vorrei creare la struttura gerarchica da questo dizionario che sarà raggruppare gli elementi in modo simile (esatta struttura non ha importanza , così come il rapporto tra gli elementi è conservato):

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

la gerarchia va come segue: array g è un prefisso di matrice h e i e quindi è il loro antenato. Ma e è un prefisso di g, quindi e è un antenato di g.

Ecco la mia idea di come ottenere questo risultato.

• Ordina il dizionario in base al numero di elementi nella lista, che sono stato in grado di raggiungere con s = sorted(a.items(), key=lambda e: len(e[1])). Questo mi darà la seguente struttura:

.

('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]) 

• In questo momento mi può trovare progenitori scorrendo elementi e controllando se un elemento è un prefisso di altri elementi. A partire dal primo. e è un prefisso di g, f e h. E c è un prefisso di a, b, d. Quindi questi due elementi sono i genitori.

• Al momento capisco che devo ricorrere alla ricorsione per entrare in ciascun genitore e per eseguire la stessa operazione, ma non sono riuscito a trovare una soluzione giusta.

Così fa qualcuno sa come affrontare questo problema. O sto complicando troppo le cose e c'è un modo più semplice per raggiungere la soluzione.

P.S. questo non è un compito a casa o una domanda di intervista (potrebbe anche esserlo). Questa è solo la mia astrazione da un problema che sto cercando di risolvere.

Answer 1

Altre persone già danno il methord, ho solo scrivere del codice qui:

Prima sorta:

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

La costruzione della struttura

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

dato un oggetto che ha una lista di bambini, e una funzione di is_prefix, e la vostra lista ordinata di oggetti, non vedo perché questo non funzionerebbe

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

Come di costruire l'albero con una serie di dizionari annidati, in modo che ci si accede al nodo e dal tree[3] e il nodo h da tree[3][3][3][3][3]: uscita

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 

Esempio:

>>> 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

appena sorta array in ordine lessicografico:

(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]) 

Poi soluzione è abbastanza evidente.

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

È necessario solo il percorso del percorso padre per prefisso. Dalla linea precedente. Formerai qualcosa come lo stack. root ha un set vuoto, quindi spingerlo in pila. c ha prefisso (vuoto) come root così root è madre di c. Spingere sullo stack c. a ha prefisso che è c in cima alla pila in modo c è madre di a. spingere a sullo stack. d ha prefisso stessa a in cima alla pila così a è madre di d e premere sulla pila. b non ha il prefisso d in cima allo stack così pop. Lo stesso per a quindi pop. Ora c'è c che è il prefisso quindi b ha il genitore c. Spingere b in pila. E continua allo stesso modo.

In Erlang semplicemente:

-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. 

e il risultato

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}] 

in Python non sarà algoritmo in modo elegante, ma nello stesso funzionerà anche.