En Python combinatoires

Question

J'ai une sorte de structure arborescente un niveau que:

Où p sont des nœuds parents, c sont des nœuds enfants et b sont hypothétique branches.

Je veux trouver tous les combinaisons des branches sous la contrainte que seulement un parent peut ramifier à seulement un nœud enfant, et deux branches ne peut pas parents d'actions et / ou de l'enfant.

par exemple. si combo est l'ensemble des combinaisons:

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

Je pense que ce tous. =)

Comment cela peut-il être achived en Python pour automaticly arbres arbitraires de cette structure à savoir le nombre de p: s, c: s et b:. S sont arbitraires

EDIT:

Il est pas un arbre mais une biparti graphe acyclique dirigé

Answer 1

Voici une façon de le faire. Il y a plein de micro-optimisations qui pourraient être apportées, mais leur efficacité dépendra de la taille en cause.

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)

Je suis assez sûr que ce soit au moins percutant la complexité optimale que je ne vois pas un moyen d'éviter de regarder toutes les combinaisons qui est unique par le parent.

Answer 2

Regardez itertools générateurs combinatoires:

produit ()
• permutations ()
• combinaisons ()
• combinations_with_replacement ()

On dirait que vous pouvez écrire un itérateur pour obtenir ce que vous voulez.