combinatorio in Python

Question

ho una sorta di una struttura ad albero di un livello come:

Dove p sono nodi padre, c sono i nodi e B bambino sono ipotetici rami.

voglio trovare tutte le combinazioni di rami sotto il vincolo che solo un genitore può espandersi a un solo una nodo figlio, e due rami non può condividere genitore e/o un bambino.

E.g. se combo è l'insieme di combinazioni:

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

Credo che sia tutti loro. =)

Come può essere eseguito automaticamente in Python per alberi arbitrari di queste strutture, cioè il numero di p: s, c: s eb: s sono arbitrari.

EDIT:

E non è un albero, ma piuttosto uno sguardo bipartitedirected acyclic graph

Answer 1

Ecco un modo per farlo. Ci sono molte micro-ottimizzazioni che potrebbero essere fatte, ma la loro efficacia dipenderebbe dalle dimensioni coinvolte.

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) 

Sono abbastanza sicuro che questo è almeno colpire complessità ottimale come io non vedo un modo per evitare di guardare ogni combinazione che è unico dal genitore.

Answer 2

a itertools generatori combinatorici:

• prodotto()
• permutazioni()
• combinazioni ()
• combination_with_replacement()

Sembra che sia possibile scrivere un iteratore per ottenere ciò che si desidera.