从 Python 列表生成层次结构
Generating a hierarchy from a Python list
我正在使用 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
中列表的第一项不包含 repeated/duplicated 元素,但 list1
中列表的第二项包含。
这个层级是怎么产生的?
注意:我可以使用一些代码来做到这一点,但它可能会很长,而且 CPU 成本可能很高(实际列表很长)。
你可以尝试使用这个递归函数,它有点冗长,可以使用列表理解重写。 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
如果您觉得有用,请点赞并采纳答案。
您可以使用广度优先搜索:
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]]
我正在使用 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
中列表的第一项不包含 repeated/duplicated 元素,但 list1
中列表的第二项包含。
这个层级是怎么产生的?
注意:我可以使用一些代码来做到这一点,但它可能会很长,而且 CPU 成本可能很高(实际列表很长)。
你可以尝试使用这个递归函数,它有点冗长,可以使用列表理解重写。 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
如果您觉得有用,请点赞并采纳答案。
您可以使用广度优先搜索:
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]]