Kombinatorik in Python

Question

Ich habe eine Art von einer Ebene Baumstruktur als:

Wo p Elternknoten, c sind untergeordnete Knoten, und b sind hypothetischen Zweige.

Ich möchte der Zweige unter der Einschränkung alle Kombinationen finden, die nur ein Elternteil nur ein Kind Knoten verzweigen, und zwei Zweige nicht teilen Eltern und/oder Kind.

z. wenn combo der Satz von Kombinationen ist:

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

Ich glaube, dass alle von ihnen ist. =)

Wie kann dies automatisch in Python für beliebige Bäume dieser Strukturen erreicht werden, d.h. die Anzahl von p: s, c: s und b: s sind willkürlich.

EDIT:

Es ist kein Baum, sondern ein bipartitedirected acyclic graph

Answer 1

Hier ist eine Möglichkeit, es zu tun. Es gibt eine Menge von Mikrooptimierungen, die gemacht werden könnten, aber ihre Wirksamkeit hängt von den beteiligten Größen ab.

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) 

Ich bin mir ziemlich sicher, dass dies zumindest ist eine optimale Komplexität schlagen, wie ich bei jeder Kombination keine Möglichkeit sehen, zu vermeiden suchen, die von Eltern einzigartig ist.

Answer 2

Blick auf itertools combinatoric Generatoren:

• Produkt()
• Permutationen()
• Kombinationen ()
• combinations_with_replacement()

Sieht so aus, als könnten Sie einen Iterator schreiben, um zu erreichen, was Sie wollen.