Combinatoria in Python

Question

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

Dove p sono nodi padre, c sono nodi e b figlio sono ipotetico rami.

Voglio trovare tutti i combinazioni di rami sotto il vincolo che solo una genitore può espandersi a solo una di nodi figlio, e due rami non puoi condividere genitore e / o un bambino.

es. 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]]

Penso che sia tutti loro. =)

Come si può achived automaticly in Python per alberi arbitrarie di queste strutture cioè il numero di p: s, c: s e B:. S sono arbitrari

EDIT:

Non è un albero, ma piuttosto una bipartito diretto acyclic graph

Answer 1

Ecco un modo per farlo. Ci sono una sacco di micro-ottimizzazioni che potrebbe essere fatto, ma la loro efficacia dipenderà 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 ottimale complessità come io non vedo un modo per evitare di guardare ogni combinazione che è unico da un genitore.

Answer 2

itertools generatori combinatorici:

• prodotto ()
• permutazioni ()
• combinazioni ()
• combinations_with_replacement ()

appare come è possibile scrivere un iteratore per ottenere ciò che si desidera.