Python Combinatoria, parte 2

Question

Ésta es una pregunta de seguimiento a Combinatorics in Python

he un árbol o grafo acíclico dirigido por así decirlo, con una estructura como:

Donde r es la raíz nodos, p son nodos principales, c son nodos hijo y b son hipotéticas ramas. Los nodos raíz no están directamente vinculados a los nodos principales, solo es una referencia.

estoy intressted en la búsqueda de todas las combinaciones de las ramas bajo las restricciones:

1. Un niño puede ser compartido por cualquier número de nodos padre, dado que estos nodos padres no comparten nodo raíz.
2. una combinación válida no debe ser un subconjunto de otra combinación

En este ejemplo sólo dos combinaciones válidas son posibles en virtud de las restricciones:

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

La estructura de datos es tal que b es una lista de objetos derivados, que tienen las propiedades r, c y p, p. ej .:

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

Answer 1

Este problema se puede resolver en Python de manera fácil y elegante, porque hay un módulo llamado "itertools".

Digamos que tenemos objetos del tipo HypotheticalBranch, que tienen atributos r, p y c. Del mismo modo que lo describió en su mensaje:

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) 

Su conjunto de ramas hipotéticas es por lo tanto

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

La función mágica que devuelve una lista de todas las posibles combinaciones de rama podría escribirse así:

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()) 

Para ser precisos, esta función devuelve un iterador. Obtenga la lista iterando sobre ella. Estas cuatro líneas de código imprimirá todas las combinaciones posibles:

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

La salida de este programa es:

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) 

... que es justo lo que quería.

Entonces, ¿qué hace el script? Crea una lista de todas las ramas hipotéticas para cada combinación (nodo raíz, nodo hijo). Y luego produce el producto de estas listas, es decir, todas las combinaciones posibles de un elemento de cada una de las listas.

Espero que tenga lo que realmente quería.

Answer 2

Su segunda restricción significa que quiere combinaciones máximas, es decir, todas las combinaciones con la longitud igual a la combinación más grande.

Me acercaría a esto atravesando primero la estructura "b" y creando una estructura, llamada "c", para almacenar todas las ramas que llegan a cada nodo secundario y categorizadas por el nodo raíz que llega a ella.

Luego, para construir combinaciones de salida, para cada elemento secundario puede incluir una entrada de cada conjunto raíz que no esté vacía. El orden (tiempo de ejecución) del algoritmo será el orden del resultado, que es lo mejor que puede obtener.

Por ejemplo, la estructura de "C", se verá así:

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

Para el ejemplo que nos ha facilitado:

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

Debe ser bastante fácil de codificar utilizando este enfoque. Solo necesita iterar sobre todas las ramas "b" y completar la estructura de datos para "c". Luego, escribe una pequeña función recursiva que recorre todos los elementos dentro de "c".

Aquí está el código (que entré en los datos de la muestra en la parte superior por el bien de pruebas):

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

Para cada niño c, con los padres hipotética p (c), con raíces r (p (c)), elija exactamente un padre p de p (c) para cada raíz r en r (p (c)) (tal que r es la raíz de p) e incluya b en la combinación donde b conecta p c (suponiendo que hay solo uno de esos b, lo que significa que no es un multigrafo). El número de combinaciones será el producto del número de padres por el cual cada niño está hipotéticamente conectado a cada raíz.En otras palabras, el tamaño del conjunto de combinaciones será igual al producto de las conexiones hipotéticas de todos los pares raíz-hijo. En su ejemplo, todos los pares raíz-hijo tienen una sola ruta, excepto r1-c2, que tiene dos rutas, por lo tanto, el tamaño del conjunto de combinaciones es dos.

Esto satisface la restricción de que ninguna combinación sea un subconjunto de otra porque al elegir exactamente un padre para cada raíz de cada elemento secundario, maximizamos las conexiones numéricas. A continuación, agregar cualquier borde b haría que su raíz se conecte a su hijo dos veces, lo cual no está permitido. Y como elegimos exactamente una, todas las combinaciones tendrán exactamente la misma longitud.

La implementación de esta opción recursivamente dará las combinaciones deseadas.

Answer 4

En realidad, hay dos problemas aquí: en primer lugar, debe resolver el algoritmo que utilizará para resolver este problema y, en segundo lugar, debe implementarlo (en Python).

---

Algoritmo

Supondré desea una máxima colección de ramas; es decir, una vez que no puede agregar más ramas. Si no lo hace, puede considerar todos los subconjuntos de una colección máxima.

Por lo tanto, para un nodo secundario queremos tomar tantas ramas como sea posible, sujeto a la restricción de que no hay dos nodos principales que compartan una raíz. En otras palabras, de cada niño puede tener como máximo un borde en la vecindad de cada nodo raíz. Esto parece sugerir que desea iterar primero sobre los hijos, luego sobre los (nodos de raíz), y finalmente sobre los bordes entre estos. Este concepto da el siguiente pseudocódigo:

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

find all combinations of permissible edges 

---

Código

>>> 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'))] 

Lo anterior parece funcionar, aunque no lo he probado.