Python Kombinatorik, Teil 2

Question

Dies ist eine Folgefrage zu Combinatorics in Python

Ich habe einen Baum oder azyklische Graph gerichtet, wenn Sie mit einer Struktur wie:

Wo r Wurzel Knoten, p sind Elternknoten, c sind Kindknoten und b sind hypothetische Verzweigungen. Die Wurzelknoten sind nicht direkt mit den übergeordneten Knoten verbunden, sondern nur eine Referenz.

ich intressted bin alle Kombinationen von Zweigen unter den Einschränkungen bei der Suche nach:

1. Ein Kind kann gegeben durch eine beliebige Anzahl von übergeordneten Knoten gemeinsam genutzt werden, dass dieser übergeordnete Knoten keine Wurzelknoten nicht teilen.
2. eine gültige Kombination sollte keine Teilmenge einer anderen

nur zwei gültige Kombinationen sind möglich unter den Einschränkungen In diesem Beispiel Kombination sein:

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

Die Datenstruktur, wie beispielsweise B ist ist eine Liste von Zweigobjekten mit den Eigenschaften r, c und p, zB:

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

Answer 1

Dieses Problem kann in Python einfach und elegant gelöst werden, denn es gibt ein Modul namens "itertools".

Nehmen wir an, wir haben Objekte vom Typ HypotheticalBranch, die die Attribute r, p und c haben. So wie Sie es in Ihrem Beitrag beschrieben:

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) 

Ihr Satz von hypothetischen Zweigen ist somit

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

Die magische Funktion, die eine Liste aller möglichen Zweige Combos gibt könnte wie so geschrieben werden:

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

Um genau zu sein, gibt diese Funktion einen Iterator zurück. Holen Sie sich die Liste, indem Sie darüber iterieren. Diese vier Zeilen Code auszudrucken, alle möglichen Kombinationen:

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

Die Ausgabe dieses Programms ist:

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) 

... das ist genau das, was Sie wollten.

Was macht das Skript? Es erstellt eine Liste aller hypothetischen Zweige für jede Kombination (Wurzelknoten, Kindknoten). Und dann ergibt es das Produkt dieser Listen, d. H. Alle möglichen Kombinationen eines Elements aus jeder der Listen.

Ich hoffe, ich habe bekommen, was Sie eigentlich wollten.

Answer 2

Die zweite Einschränkung bedeutet, dass Sie maximale Kombinationen wünschen, d. H. Alle Kombinationen mit der Länge, die der größten Kombination entspricht.

Ich würde dies erreichen, indem ich zuerst die "b" -Struktur durchquere und eine Struktur namens "c" erstelle, um alle Zweige zu speichern, die zu jedem Kindknoten kommen und durch den Wurzelknoten kategorisiert werden.

Dann, um Kombinationen für die Ausgabe zu konstruieren, können Sie für jedes Kind einen Eintrag aus jedem Wurzelsatz aufnehmen, der nicht leer ist. Die Reihenfolge (Ausführungszeit) des Algorithmus ist die Reihenfolge der Ausgabe, die die beste ist, die Sie erhalten können.

Zum Beispiel Ihre "c" Struktur wird wie folgt aussehen:

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

Für das Beispiel, das Sie zur Verfügung gestellt:

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

Es sollte ziemlich einfach sein, es zu codieren mit diesem Ansatz. Sie müssen nur über alle Zweige "b" iterieren und die Datenstruktur für "c" füllen. Schreiben Sie dann eine kleine rekursive Funktion, die alle Elemente in "c" durchläuft.

Hier ist der Code (I Ihre Beispieldaten an der Spitze für die Prüfung Sake eingegeben):

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

Für jedes Kind c, mit hypothetischen Eltern p (c), mit Wurzeln r (p (c)), wähle genau einen Elternteil p aus p (c) für jede Wurzel r in r (p (c)) (so dass r die Wurzel von p ist) und b in die Kombination einbezieht, in der b p mit c verbindet (vorausgesetzt, es gibt nur ein solches b, was bedeutet, dass es kein Multigraph ist). Die Anzahl der Kombinationen ergibt sich aus der Anzahl der Eltern, mit denen jedes Kind hypothetisch mit jeder Wurzel verbunden ist.Mit anderen Worten, die Größe der Menge der Kombinationen ist gleich dem Produkt der hypothetischen Verbindungen aller Kind-Wurzel-Paare. In Ihrem Beispiel haben alle diese Kind-Wurzel-Paare nur einen Pfad, mit Ausnahme von r1-c2, der zwei Pfade hat, so dass die Größe des Satzes von Kombinationen zwei ist.

Dies erfüllt die Einschränkung, dass keine Kombination eine Teilmenge einer anderen ist, da durch die Auswahl genau eines Elternteils für jede Wurzel jedes Kindes die Anzahl der Verbindungen maximiert wird. Nach dem Hinzufügen einer beliebigen Kante b würde ihr Stamm zweimal mit seinem Kind verbunden, was nicht erlaubt ist. Und da wir genau eins wählen, sind alle Kombinationen genau gleich lang.

Wenn Sie diese Auswahl rekursiv durchführen, erhalten Sie die gewünschten Kombinationen.

Answer 4

Es gibt wirklich zwei Probleme hier: erstens müssen Sie den Algorithmus ausarbeiten, den Sie verwenden, um dieses Problem zu lösen, und zweitens müssen Sie es implementieren (in Python).

---

Algorithmus

Ich werde annehmen, dass Sie eine maximal Sammlung von Filialen wollen; das heißt, zu dem Sie keine weiteren Zweige hinzufügen können. Wenn Sie dies nicht tun, können Sie alle Teilmengen einer maximalen Sammlung berücksichtigen.

Daher möchten wir für einen untergeordneten Knoten so viele Zweige wie möglich verwenden, wobei die Einschränkung gilt, dass keine zwei übergeordneten Knoten einen Stamm gemeinsam haben. Mit anderen Worten, von jedem Kind können Sie höchstens eine Kante in der Nachbarschaft jedes Wurzelknotens haben. Dies scheint darauf hinzudeuten, dass Sie zuerst über die Kinder, dann über die (Nachbarschaften der) Wurzelknoten und schließlich über die Kanten zwischen diesen iterieren möchten. Dieses Konzept gibt den folgenden Pseudo-Code:

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

Die oben scheint zu funktionieren, obwohl ich es nicht getestet haben.