我有的：
我有一個元組串列。這些元組的第一項表示目錄中檔案夾的級別，而第二項表示檔案夾的名稱。這些元組也是根據它們與
串列如下所示：
single_paths = [
[0, "1st Top Level Folder"],
[1, "1st Child To 1st Top Level Folder"],
[2, "1st Grandchild To 1st Child Folder"],
[2, "2nd Grandchild To 1st Child Folder"],
[1, "2nd Child To 1st Top Level Folder"],
[2, "1st Grandchild To 2nd Child Folder"],
[0, "2nd Top Level Folder"],
[1, "1st Child To 2nd Top Level Folder"],
[0, "3rd Top Level Folder"],
]
目錄樹的可視化表示：
我想要實作的目標： 所有可能路徑的串列，如下所示：
possible_paths = [
["1st Top Level Folder"],
["1st Top Level Folder", "1st Child To 1st Top Level Folder"],
["1st Top Level Folder", "1st Child To 1st Top Level Folder", "1st Grandchild To 1st Child Folder"],
["1st Top Level Folder", "1st Child To 1st Top Level Folder", "2nd Grandchild To 1st Child Folder"],
["1st Top Level Folder", "2nd Child To 1st Top Level Folder"],
["1st Top Level Folder", "2nd Child To 1st Top Level Folder", "1st Grandchild To 2nd Child Folder"],
["2nd Top Level Folder"],
["2nd Top Level Folder", "1st Child To 2nd Top Level Folder"],
["3rd Top Level Folder"],
]
你會推薦什么演算法來實作這一目標？我已經花了 3 天的時間，似乎無法得到正確的結果。提前感謝您的幫助。
uj5u.com熱心網友回復：
由于級別是有序的，一旦級別比以前小，您就可以上升某些級別：
possible_paths = []
for i, (level, name) in enumerate(single_paths):
if level == 0:
cur_path = []
elif level <= single_paths[i-1][0]:
cur_path = cur_path[:-(1 single_paths[i-1][0] - level)]
cur_path.append(name)
possible_paths.append(cur_path[:])
uj5u.com熱心網友回復：
也發布我的，只是因為我在注意到已經發布了 2 個幾乎相同的答案之前已經完成了它。
result = []
cur_level = -1
cur_path = []
for level, name in single_paths:
if level<=cur_level:
cur_path = cur_path[:level]
cur_path.append(name)
result.append(cur_path.copy())
cur_level = level
uj5u.com熱心網友回復：
我會推薦最簡單的演算法;)
single_paths = [
[0, "1st Top Level Folder"],
[1, "1st Child To 1st Top Level Folder"],
[2, "1st Grandchild To 1st Child Folder"],
[2, "2nd Grandchild To 1st Child Folder"],
[1, "2nd Child To 1st Top Level Folder"],
[2, "1st Grandchild To 2nd Child Folder"],
[0, "2nd Top Level Folder"],
[1, "1st Child To 2nd Top Level Folder"],
[0, "3rd Top Level Folder"],
]
stack = []
for node in single_paths:
if stack:
top = stack[-1]
while stack and top[0] >= node[0]:
top = stack.pop()
stack.append(node)
print(stack) # you can store it too, res.append([el[1] for el in stack])
通常我們將當前路徑中的所有節點存盤在堆疊中。如果下一個節點級別更大，我們只需將它附加到路徑，但如果不是，我們需要從路徑中洗掉盡可能多的節點，直到我們在小于處理節點級別的級別上停止。
uj5u.com熱心網友回復：
您可以使用遞回：
from itertools import groupby
def to_tree(d, j=[]):
k = [(a, list(b)) for a, b in groupby(d, key=lambda x:not x[0])]
for i in range(0, len(k), 2):
for _, p in k[i][-1]:
yield j p
if i 1 < len(k):
yield from to_tree([[a-1, b] for a, b in k[i 1][-1]],j p)
data = [[0, '1st Top Level Folder'], [1, '1st Child To 1st Top Level Folder'], [2, '1st Grandchild To 1st Child Folder'], [2, '2nd Grandchild To 1st Child Folder'], [1, '2nd Child To 1st Top Level Folder'], [2, '1st Grandchild To 2nd Child Folder'], [0, '2nd Top Level Folder'], [1, '1st Child To 2nd Top Level Folder'], [0, '3rd Top Level Folder']]
r = list(to_tree([[a, [b]] for a, b in data]))
輸出：
[['1st Top Level Folder'],
['1st Top Level Folder', '1st Child To 1st Top Level Folder'],
['1st Top Level Folder', '1st Child To 1st Top Level Folder', '1st Grandchild To 1st Child Folder'],
['1st Top Level Folder', '1st Child To 1st Top Level Folder', '2nd Grandchild To 1st Child Folder'],
['1st Top Level Folder', '2nd Child To 1st Top Level Folder'],
['1st Top Level Folder', '2nd Child To 1st Top Level Folder', '1st Grandchild To 2nd Child Folder'],
['2nd Top Level Folder'],
['2nd Top Level Folder', '1st Child To 2nd Top Level Folder'],
['3rd Top Level Folder']]
更短的解決方案：
p = {}
r = [(p:={a:[b],'r':[b]})['r'] if not a else (p:={**p,a:(v:=(p[a-1] [b])),'r':v})['r']
for a, b in data]
輸出：
[['1st Top Level Folder'],
['1st Top Level Folder', '1st Child To 1st Top Level Folder'],
['1st Top Level Folder', '1st Child To 1st Top Level Folder', '1st Grandchild To 1st Child Folder'],
['1st Top Level Folder', '1st Child To 1st Top Level Folder', '2nd Grandchild To 1st Child Folder'],
['1st Top Level Folder', '2nd Child To 1st Top Level Folder'],
['1st Top Level Folder', '2nd Child To 1st Top Level Folder', '1st Grandchild To 2nd Child Folder'],
['2nd Top Level Folder'],
['2nd Top Level Folder', '1st Child To 2nd Top Level Folder'],
['3rd Top Level Folder']]
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/391643.html