Kombinatorik in Python

Question

Ich habe eine Art einstufige Baumstruktur als:

Wobei P übergeordnete Knoten sind, C sind Kinderknoten und B hypothetisch Geäst.

Ich möchte alles finden Kombinationen von Zweigen unter der Einschränkung, dass nur eines Eltern können nur noch verzweigen eines Kinderknoten und zwei Zweige können Eltern und/oder Kind nicht teilen.

ZB if combo ist der Satz von Kombinationen:

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 denke, das sind alle. =))

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

BEARBEITEN:

Es ist kein Baum, sondern ein Baum Bippartiziten Regie acyclische Graphen

Answer 1

Hier ist eine Möglichkeit, es zu tun. Es gibt viele Mikrooptimierungen, die vorgenommen werden könnten, aber ihre Wirksamkeit würde von den damit verbundenen Größen abhängen.

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 die optimale Komplexität erreicht, da ich keinen Weg sehe, um zu vermeiden, dass jede Kombination, die von Eltern einzigartig ist, eindeutig ist.

Answer 2

Ansehen ITertools Kombinatorgeneratoren:

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

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