从一个列表字典创建层次结构

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. 这不是作业或面试题（也可能是）。这只是我尝试解决问题时的抽象。

- Salvador Dali

---

我真的不明白为什么需要递归（虽然我确定它可以以某种方式使用）。要在n^2中完成，对于每个元素，检查所有其他元素以查看它们是否是其子元素。之后你就完成了... - Hammer

你不需要检查所有其他元素，只需检查在已排序列表（按长度）中它之后的元素。 - Hammer

在我看来，你似乎正在寻找一种Trie（也称为前缀树）。请参见维基百科上的Trie - Catalin Pol

Answer 1

其他人已经给出了方法，我这里只是写了一些代码：

首先进行排序：

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

- PasteBT

---

@SalvadorDali 我在Python 2.7.3和Linux上尝试了一下，它返回 {'c': {'a': {'d': {}}, 'b': {}}, 'e': {'g': {'i': {}, 'h': {}}, 'f': {}}}。 - PasteBT

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)

- Hammer

Answer 3

如何使用一组嵌套字典构建树，这样您可以通过 tree[3] 访问 e 节点，通过 tree[3][3][3][3][3] 访问 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"
    }
}

- Blckknght

---

感谢您的帮助，但它看起来完全不同于我期望得到的。 - Salvador Dali

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推入堆栈。以相同的方式继续。

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

在Python中，它可能不会那么优雅，但相同的算法也可以工作。

- Hynek -Pichi- Vychodil

---

谢谢，我会先尝试在Erlang中进行测试。 - Salvador Dali