构建目录路径列表的正确算法是什么?

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']]