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