Combinatoria en Python

Question

que tienen una especie de estructura de árbol de una sola planta como:

Donde p son nodos padre, c son nodos secundarios y B son hipotéticos ramas.

Quiero encontrar todas las combinaciones de ramas bajo la restricción de que sólo uno padre puede ramificarse a solamente uno nodo hijo, y dos ramas no puede compartir los padres y/o el niño.

E.g. Si combo es el conjunto de combinaciones:

combo[0] = [b[0], b[3]] 
combo[1] = [b[0], b[4]] 
combo[2] = [b[1], b[4]] 
combo[3] = [b[2], b[3]] 

Creo que eso es todo de ellos. =)

Cómo se puede lograr esto automáticamente en Python para árboles arbitrarios de estas estructuras, es decir, el número de p: s, c: s y b: s son arbitrarios.

EDIT:

No es un árbol, sino más bien una mirada bipartitedirected acyclic graph

Answer 1

Aquí hay una manera de hacerlo. Hay muchas micro optimizaciones que podrían hacerse, pero su eficacia dependería de los tamaños involucrados.

import collections as co 
import itertools as it 

def unique(list_): 
    return len(set(list_)) == len(list_) 

def get_combos(branches): 
    by_parent = co.defaultdict(list) 

    for branch in branches: 
     by_parent[branch.p].append(branch) 

    combos = it.product(*by_parent.values()) 

    return it.ifilter(lambda x: unique([b.c for b in x]), combos) 

estoy bastante seguro de que esto es al menos golpear la complejidad óptima, ya que no veo una manera de evitar mirar a cada combinación que es única por el padre.

Answer 2

en itertools generadores combinatoric:

• de productos()
• permutaciones()
• combinaciones ()
• combinations_with_replacement()

Parece que puede escribir un iterador para lograr lo que desea.