Combinatoire en Python

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étiques branches.

Je veux trouver toutes les combinaisons de branches sous la contrainte que seul un parent branche peut seulement un nœud enfant, et deux branches ne peut pas partager des parents et/ou enfants.

E.g. 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 obtenu automatiquement en Python pour des arbres arbitraires de ces structures, c'est-à-dire que le nombre de p: s, c: s et b: s est arbitraire.

EDIT:

Il n'est pas un arbre mais une bipartitedirected acyclic graph

Answer 1

Voici une façon de le faire. Il y a beaucoup de micro-optimisations qui pourraient être faites mais leur efficacité dépendrait des tailles impliquées.

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 sûr que ce soit au moins frapper la complexité optimale car 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 réaliser ce que vous voulez.