从Python列表生成层次结构

Question

我正在使用Python 3.8

以下列表包含整数，我需要从此列表生成层次结构：

list1 = [[15, 1], [22, 1], [23, 1], [121, 15], [101, 22], [105, 23], [106, 23], [108, 23], [155, 121], [120, 108], [19, 2], [25, 5], [33, 8], [35, 8], [28, 25], [29, 28]]

我需要这个结果（输出可以是一个列表，例如[[[1, 15, 22, 23], [15, 121], [121, 155], [22, 101], [23, 105, 106, 108], [108, 120]], [2, 19], [[5, 25], [25, 28], [28, 29]], [8, 33, 35]]）：

1 ---- 15 ---- 121 ---- 155
 \---- 22 ---- 101
  \--- 23 ---- 105
        \----- 106
         \---- 108 ---- 120

2 ---- 19

5 ---- 25 ---- 28 ----- 29

8 ---- 33
 \---- 35

层次结构不包含任何重复项。另外list1中列表的第一项不包含重复/重复的元素，但list1中列表的第二项包含重复/重复的元素

如何生成此层次结构

注意：我可以通过使用一些代码来实现这一点，但它可能非常长，CPU成本可能很高（实际列表非常长）

Answer 1

您可以使用广度优先搜索：

from collections import deque, defaultdict
list1 = [[15, 1], [22, 1], [23, 1], [121, 15], [101, 22], [105, 23], [106, 23], [108, 23], [155, 121], [120, 108], [19, 2], [25, 5], [33, 8], [35, 8], [28, 25], [29, 28]]
def get_levels():
   q, r, d = deque(sorted({(b, b) for a, b in list1 if all(k != b for k, _ in list1)})), [], defaultdict(list)
   while q:
      r.append(((n:=q.popleft())[0], [n[-1], *(l:=[a for a, b in list1 if b == n[-1]])]))
      q.extend([(n[0], i) for i in l])
   for a, b in r:
      if len(b) > 1:
         d[a].append(b)
   return [i for b in d.values() for i in ([b] if len(b) > 1 else b)]

print(get_levels())

输出：

[[[1, 15, 22, 23], [15, 121], [22, 101], [23, 105, 106, 108], [121, 155], [108, 120]], [2, 19], [[5, 25], [25, 28], [28, 29]], [8, 33, 35]]

Answer 2

您可以尝试使用这个递归函数，它有点冗长，可以使用列表理解重新编写need是您的预期输出

list1 = [[15, 1], [22, 1], [23, 1], [121, 15], [101, 22], [105, 23], [106, 23], [108, 23], [155, 121], [120, 108], [19, 2], [25, 5], [33, 8], [35, 8], [28, 25], [29, 28]]

need = [[[1, 15, 22, 23], [15, 121], [121, 155], [22, 101], [23, 105, 106, 108], [108, 120]], [2, 19], [[5, 25], [25, 28], [28, 29]], [8, 33, 35]]

graph = {}

for y, x in list1:
    graph.setdefault(x, []).append(y)

def form_graph(graph):
    seen = set()

    def form(k, v):
        if k in seen:
            return []
        res = [[k]]
        res[-1].extend(v)
        seen.add(k)

        for i in v:
            if i in graph:
                res.extend(form(i, graph[i]))
        return res

    result = []
    for k, v in graph.items():
        temp = form(k, v)
        if temp:
            if len(temp) == 1:
                temp = temp[0]
            result.append(temp)
    return result

输出

print(form_graph(graph))
[[[1, 15, 22, 23], [15, 121], [121, 155], [22, 101], [23, 105, 106, 108], [108, 120]], [2, 19], [[5, 25], [25, 28], [28, 29]], [8, 33, 35]]

print(need == form_graph(graph))
True

如果你觉得这有用，请投票并接受答案