0
435
Views¿Cuál es el algoritmo correcto para crear una lista de rutas de directorio?
Lo que tengo:
Tengo una lista de tuplas. El primer elemento de estas tuplas representa el nivel de una carpeta en un directorio, mientras que el segundo elemento representa el nombre de la carpeta. Estas tuplas también están ordenadas según su relación con el
Así es como se ve la lista:
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"], ]Representación visual del árbol de directorios:
Lo que quiero lograr: una lista de todos los caminos posibles que se vea así:
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"], ]¿Qué algoritmo recomendarías para lograr esto? He pasado 3 días en esto y parece que no puedo obtener el resultado correcto. Gracias por su ayuda de antemano.
3 answers
Answer question0
Dado que los niveles están ordenados, puede subir ciertos niveles una vez que los niveles sean más pequeños que los anteriores:
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[:])0
Publicando el mío también, solo porque ya lo completé antes de notar que ya se publicaron 2 respuestas casi idénticas.
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 = level0
Recomendaría el algoritmo más simple jamás;)
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])Generalmente almacenamos en la pila todos los nodos en la ruta actual. Si el siguiente nivel de nodo es más grande, simplemente lo agregamos a la ruta, pero si no, debemos eliminar la mayor cantidad de nodos de la ruta hasta que nos detengamos en un nivel más pequeño que el nivel del nodo de procesamiento.