从列表的字典创建层次

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

如何与建筑树一组嵌套的字典，这样就会通过tree[3][3][3][3][3]访问由tree[3]的e节点和节点h：

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 

您只需要通过前缀跟踪父路径表单。从前一行开始。你会形成一些像堆栈一样的思维。 root有空集，因此将其推入堆栈。 c具有（空）前缀作为根，因此root是c的父项。在堆栈上推c。 a的前缀是c，所以c是a的父亲。在堆栈上推a。 d在堆栈顶部具有与a相同的前缀，因此a是d的父代，并推入堆栈。 b在堆栈顶部没有前缀d弹出。 a然后弹出。现在有c这是前缀所以b有父母c。在堆栈上推b。并继续以同样的方式。

在二郎简单：

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

在蟒蛇也不会那么优雅，但同样的算法也可以工作。