构建目录路径列表的正确算法是什么?
What's the right algorithm to build a list of directory paths?
我有:
我有一个元组列表。这些元组的第一项代表目录中文件夹的级别,而第二项代表文件夹的名称。这些元组也按照它们与
的关系排序
列表如下所示:
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 天,似乎无法得到正确的结果。提前感谢您的帮助。
我会推荐最简单的算法 ;)
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])
一般我们把当前路径上的所有节点都存储在栈中。如果下一个节点级别更大,我们只需将其附加到路径,但如果不是,我们需要从路径中删除尽可能多的节点,直到我们停止在小于处理节点级别的级别。
由于等级是有序的,一旦等级低于之前的等级,您就可以上升到特定等级:
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[:])
也发布我的,只是因为我已经完成了它,然后才注意到已经发布了 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
你可以使用递归:
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']]
我有:
我有一个元组列表。这些元组的第一项代表目录中文件夹的级别,而第二项代表文件夹的名称。这些元组也按照它们与
的关系排序列表如下所示:
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 天,似乎无法得到正确的结果。提前感谢您的帮助。
我会推荐最简单的算法 ;)
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])
一般我们把当前路径上的所有节点都存储在栈中。如果下一个节点级别更大,我们只需将其附加到路径,但如果不是,我们需要从路径中删除尽可能多的节点,直到我们停止在小于处理节点级别的级别。
由于等级是有序的,一旦等级低于之前的等级,您就可以上升到特定等级:
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[:])
也发布我的,只是因为我已经完成了它,然后才注意到已经发布了 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
你可以使用递归:
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']]