What's the right algorithm to build a list of directory paths?-CodePudding

What I have:

I have a list of tuples. The first item of these tuples represent the level of a folder in a directory, while the second item represents the name of the folder. These tuples are also ordered according to their relationship with the

Here's what the list looks like:

    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"],
                   ]

Visual Representation of the Directory Tree:

What I want to achieve: A list of all possible paths that looks like this:

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"],
                 ]

What algorithm would you recommend to achieve this? I have spent 3 days on this and can't seem to get the right result. Thanks for your help in advance.

CodePudding user response：

Since the levels are ordered you could just go up certain levels once the levels are smaller than previous:

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[:])

CodePudding user response：

Posting mine as well, just because I already completed it before noticing 2 almost identical answers were already posted.

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

CodePudding user response：

I would recommend simplest algorithm ever ;)

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

Generally we store in stack all nodes in current path. If next node level is bigger, we just append it to the path, but if not, we need to remove as much nodes from path until we stop on level smaller than level of processing node.

CodePudding user response：

You can use recursion:

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

Output:

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

Shorter solution:

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]

Output:

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