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

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:

enter image description here

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.

>Solution :

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

Leave a Reply