Python Combinatoire, partie 2

Question

Ceci est une question de suivi Combinatorics in Python

je un arbre ou graphe orienté acyclique si vous voulez une structure:

Où r sont racine nœuds, p sont des nœuds parents, c sont des nœuds enfants et b sont hypothétiques branches. Les nœuds racine ne sont pas directement liés aux nœuds parents, ce n'est qu'une référence.

J'intressted à trouver toutes les combinaisons de branches sous les contraintes:

1. Un enfant peut être partagé par un certain nombre de nœuds parents étant donné que ces nœuds parents ne partagent pas le noeud racine.
2. Une combinaison valide ne doit pas être un sous-ensemble d'une autre combinaison

Dans cet exemple, seulement deux combinaisons valides sont possibles sous les contraintes:

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

La structure de données est telle que b est une liste d'objets de branche, qui ont les propriétés r, c et p, par exemple:

b[3].r = 1 
b[3].p = 3 
b[3].c = 2 

Answer 1

Ce problème peut être résolu facilement et élégamment en Python, car il existe un module appelé "itertools". Disons que nous avons des objets de type HypotheticBranch, qui ont des attributs r, p et c.

Tout comme vous l'avez décrit dans votre message:

class HypotheticalBranch(object): 
    def __init__(self, r, p, c): 
    self.r=r 
    self.p=p 
    self.c=c 
    def __repr__(self): 
    return "HypotheticalBranch(%d,%d,%d)" % (self.r,self.p,self.c) 

Votre ensemble de branches hypothétiques est donc

b=[ HypotheticalBranch(0,0,0), 
    HypotheticalBranch(0,1,1), 
    HypotheticalBranch(1,2,1), 
    HypotheticalBranch(1,3,2), 
    HypotheticalBranch(1,4,2) ] 

La fonction magique qui retourne une liste de tous les combos de branche possibles pourrait être écrit comme ceci:

import collections, itertools 

def get_combos(branches): 
    rc=collections.defaultdict(list) 
    for b in branches: 
    rc[b.r,b.c].append(b) 
    return itertools.product(*rc.values()) 

Pour être précis, cette fonction renvoie un itérateur. Obtenez la liste en itérant sur elle. Ces quatre lignes de code vous permet d'imprimer tous les combos possibles:

for combo in get_combos(b): 
    print "Combo:" 
    for branch in combo: 
    print " %r" % (branch,) 

La sortie de ce programme est:

Combo: 
    HypotheticalBranch(0,1,1) 
    HypotheticalBranch(1,3,2) 
    HypotheticalBranch(0,0,0) 
    HypotheticalBranch(1,2,1) 
Combo: 
    HypotheticalBranch(0,1,1) 
    HypotheticalBranch(1,4,2) 
    HypotheticalBranch(0,0,0) 
    HypotheticalBranch(1,2,1) 

... ce qui est exactement ce que vous vouliez.

Alors, que fait le script? Il crée une liste de toutes les branches hypothétiques pour chaque combinaison (nœud racine, nœud enfant). Ensuite, il produit le produit de ces listes, c'est-à-dire toutes les combinaisons possibles d'un élément de chacune des listes.

J'espère avoir obtenu ce que vous vouliez réellement.

Answer 2

Votre seconde contrainte signifie que vous voulez des combinaisons maximales, c'est-à-dire toutes les combinaisons dont la longueur est égale à la plus grande combinaison. J'aborderais ceci en parcourant d'abord la structure "b" et en créant une structure, nommée "c", pour stocker toutes les branches arrivant à chaque nœud enfant et catégorisées par le nœud racine qui vient à lui. Puis, pour construire des combinaisons pour la sortie, pour chaque enfant, vous pouvez inclure une entrée de chaque ensemble racine qui n'est pas vide. L'ordre (temps d'exécution) de l'algorithme sera l'ordre de la sortie, qui est le meilleur que vous pouvez obtenir.

Par exemple, votre structure "c", ressemblera à ceci:

c[i][j] = [b_k0, ...] 
--> means c_i has b_k0, ... as branches that connect to root r_j) 

Pour l'exemple que vous avez fourni:

c[0][0] = [0] 
c[0][1] = [] 
c[1][0] = [1] 
c[1][1] = [2] 
c[2][0] = [] 
c[2][1] = [3, 4] 

Il devrait être assez facile à coder en utilisant cette approche. Vous avez juste besoin de parcourir toutes les branches "b" et remplir la structure de données pour "c". Ensuite, écrivez une petite fonction récursive qui passe par tous les éléments à l'intérieur de "c".

Voici le code (je suis entré dans vos données d'échantillon au sommet pour cause de test):

class Branch: 
    def __init__(self, r, p, c): 
    self.r = r 
    self.p = p 
    self.c = c 

b = [ 
    Branch(0, 0, 0), 
    Branch(0, 1, 1), 
    Branch(1, 2, 1), 
    Branch(1, 3, 2), 
    Branch(1, 4, 2) 
    ] 

total_b = 5 # Number of branches 
total_c = 3 # Number of child nodes 
total_r = 2 # Number of roots 

c = [] 
for i in range(total_c): 
    c.append([]) 
    for j in range(total_r): 
    c[i].append([]) 

for k in range(total_b): 
    c[b[k].c][b[k].r].append(k) 

combos = [] 
def list_combos(n_c, n_r, curr): 
    if n_c == total_c: 
    combos.append(curr) 
    elif n_r == total_r: 
    list_combos(n_c+1, 0, curr) 
    elif c[n_c][n_r]: 
     for k in c[n_c][n_r]: 
     list_combos(n_c, n_r+1, curr + [b[k]]) 
    else: 
    list_combos(n_c, n_r+1, curr) 

list_combos(0, 0, []) 

print combos 

Answer 3

Pour chaque enfant c, avec les parents hypothétique p (c), avec des racines r (p (c)), choisissez exactement un parent p de p (c) pour chaque racine r dans r (p (c)) (tel que r est la racine de p) et incluez b dans la combinaison où b relie p à c (en supposant qu'il y ait seulement un tel b, ce qui signifie que ce n'est pas un multigraph). Le nombre de combinaisons sera le produit du nombre de parents par lequel chaque enfant est hypothétiquement relié à chaque racine.En d'autres termes, la taille de l'ensemble des combinaisons sera égale au produit des connexions hypothétiques de toutes les paires enfant-racine. Dans votre exemple, toutes ces paires enfant-racine n'ont qu'un seul chemin, sauf r1-c2, qui a deux chemins, donc la taille de l'ensemble des combinaisons est deux. Cela satisfait la contrainte qu'aucune combinaison ne soit un sous-ensemble d'une autre parce qu'en choisissant exactement un parent pour chaque racine de chaque enfant, nous maximisons les connexions numériques. Par la suite ajouter un bord b ferait que sa racine soit connectée deux fois à son enfant, ce qui n'est pas autorisé. Et puisque nous en choisissons exactement un, toutes les combinaisons auront exactement la même longueur.

L'implémentation de ce choix récursivement donnera les combinaisons désirées.

Answer 4

Il y a vraiment deux problèmes ici: premièrement, vous devez élaborer l'algorithme que vous utiliserez pour résoudre ce problème et deuxièmement, vous devez l'implémenter (en Python).

---

algorithme

Je suppose que vous voulez une maximale collection de branches; c'est-à-dire, une fois que vous ne pouvez plus ajouter d'autres branches. Si vous ne le faites pas, vous pouvez considérer tous les sous-ensembles d'une collection maximale. Par conséquent, pour un nœud enfant, nous voulons prendre autant de branches que possible, sous réserve de la contrainte que deux nœuds parents ne partagent pas une racine. En d'autres termes, à partir de chaque enfant, vous pouvez avoir au plus un bord dans le voisinage de chaque nœud racine. Cela semble suggérer que vous voulez itérer d'abord sur les enfants, puis sur les (voisins des) nœuds racines, et enfin sur les bords entre ceux-ci. Ce concept donne le pseudo-code suivant:

for each child node: 
    for each root node: 
     remember each permissible edge 

find all combinations of permissible edges 

---

code

>>> import networkx as nx 
>>> import itertools 
>>> 
>>> G = nx.DiGraph() 
>>> G.add_nodes_from(["r0", "r1", "p0", "p1", "p2", "p3", "p4", "c0", "c1", "c2"]) 
>>> G.add_edges_from([("r0", "p0"), ("r0", "p1"), ("r1", "p2"), ("r1", "p3"), 
...     ("r1", "p4"), ("p0", "c0"), ("p1", "c1"), ("p2", "c1"), 
...     ("p3", "c2"), ("p4", "c2")]) 
>>> 
>>> combs = set() 
>>> leaves = [node for node in G if not G.out_degree(node)] 
>>> roots = [node for node in G if not G.in_degree(node)] 
>>> for leaf in leaves: 
...  for root in roots: 
...   possibilities = tuple(edge for edge in G.in_edges_iter(leaf) 
...        if G.has_edge(root, edge[0])) 
...   if possibilities: combs.add(possibilities) 
... 
>>> combs 
set([(('p1', 'c1'),), 
    (('p2', 'c1'),), 
    (('p3', 'c2'), ('p4', 'c2')), 
    (('p0', 'c0'),)]) 
>>> print list(itertools.product(*combs)) 
[(('p1', 'c1'), ('p2', 'c1'), ('p3', 'c2'), ('p0', 'c0')), 
(('p1', 'c1'), ('p2', 'c1'), ('p4', 'c2'), ('p0', 'c0'))] 

Ce qui précède semble fonctionner, même si je ne l'ai pas testé.