Combinatoria en Python

Question

Tengo una especie de estructura de árbol de una sola planta como:

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

Quiero encontrar todos los combinaciones de las ramas bajo la restricción de que sólo un padre puede ramificarse a sólo un de nodo secundario, y dos ramas no podemos compartir con los padres y / o hijos.

por ejemplo. 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 achived automaticamente en Python para árboles arbitrarias de estas estructuras es decir, el número de p: s, c: s y B:. S son arbitrarias

EDIT:

No es un árbol, sino más bien una bipartita dirigido acíclico gráfico

Answer 1

Aquí hay una manera de hacerlo. Hay mucho de la de micro-optimizaciones que se podrían hacer pero su eficacia dependerá de los tamaños implicados.

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 óptimo de golpeo complejidad, ya que no veo una manera de evitar mirar a cada combinación que es única por el padre.

Answer 2

itertools generadores combinatoric:

• producto ()
• permutaciones ()
• combinaciones ()
• combinations_with_replacement ()

parece que se puede escribir un iterador para lograr lo que desea.