Python: combinaciones de jerarquía de elementos primarios y secundarios

for-loop iteration

Question

Para una tabla de relación padre-hijo (csv), estoy tratando de recopilar posibles cadenas de combinación de relación padre-hijo usando todos los datos en la tabla. Estoy intentando contra un problema donde si existen múltiples sub-padres (ver filas 3 y 4), la segunda combinación de sub-padres (fila 4) no está incluida en la iteración.

Ejemplo de datos:

niño, padre

A,B
A,C
B,D
B,C
C,D

Resultados de cadena esperados:

D|B|A
D|C|B|A
D|C|A

Resultados de cadena reales:

D|B|A
D|C|A

Código

find= ''A'' #The child for which the code should find all possible parent relationships
sequence = ''''
with open(''testing.csv'',''r'') as f: #testing.csv = child,parent table (above example)
for row in f:
if row.strip().startswith(find):
parent = row.strip().split('','')[1]
sequence = parent + ''|'' + find
f1 = open(''testing.csv'',''r'')
for row in f1:
if row.strip().startswith(parent):
parent2 = row.strip().split('','')[1]
sequence = parent2 + ''|'' + sequence
parent = parent2
else:
continue
print sequence

Answer 1

¿Has mirado este fantástico ensayo? Es esencial leer para comprender realmente los patrones en Python. Su problema puede ser considerado como un problema de gráfico: encontrar las relaciones es básicamente encontrar todas las rutas desde un nodo hijo al nodo padre.

Dado que podría haber una cantidad arbitraria de anidamiento (child-> parent1-> parent2 ...), necesita una solución recursiva para encontrar todas las rutas. En tu código, tienes 2 bucles for , que solo darán como resultado 3 rutas de nivel como máximo.

El código a continuación fue adaptado del enlace de arriba para solucionar su problema. La función find_all_paths requiere un gráfico como entrada.

Vamos a crear el gráfico de tu archivo:

graph = {} # Graph is a dictionary to hold our child-parent relationships.
with open(''testing.csv'',''r'') as f:
for row in f:
child, parent = row.split('','')
graph.setdefault(parent, []).append(child)
print graph

con su muestra, esto debería imprimir:

{''C'': [''A'', ''B''], ''B'': [''A''], ''D'': [''B'', ''C'']}

El siguiente código es directamente del ensayo:

def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not graph.has_key(start):
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
for path in find_all_paths(graph, ''D'', ''A''):
print ''|''.join(path)

Salida:

D|B|A
D|C|A
D|C|B|A

Answer 2

No estoy seguro de si esta es la manera más eficiente de hacerlo (pero leer el archivo de nuevo en cada fila sería peor).

find= ''A'' #The child for which the code should find all possible parent relationships
sequences = set(find)
# we''ll build up a chain for every relationship, then strip out un-needed ones later
with open(''testing.csv'',''r'') as f: #testing.csv = child,parent table (above example)
for row in f:
child, parent = row.strip().split('','')
sequences.add(parent + ''|'' + child)
for c in sequences.copy():
if c[0] == child:
sequences.add(parent + ''|'' + c)
# remove any that don''t end with our child:
sequences = set(s for s in sequences if s.endswith(find))
# get all shorter chains when we have a longer one
extra = set()
for g1 in sequences:
for g2 in sequences:
if g2[2:] == g1:
extra.add(g1)
# remove the shorter chains
sequences.difference_update(extra)
for chain in sequences:
print(chain)

Resultados:

D|C|A
D|C|B|A
D|B|A