अजगर संयोजन विज्ञान, भाग 2

Question

यह Combinatorics in Python

लिए एक अनुवर्ती प्रश्न मैं एक पेड़ या के रूप में एक संरचना के साथ अचक्रीय ग्राफ यदि आप का निर्देशन किया है है नोड्स, पी पैरेंट नोड्स हैं, सी बच्चे नोड्स हैं और बी hypothetical शाखाएं हैं। रूट नोड सीधे पैरेंट नोड्स से जुड़े नहीं होते हैं, यह केवल एक संदर्भ है।

मैं सीमा के अन्दर शाखाओं के सभी संयोजनों को खोजने में intressted हूँ:

1. एक बच्चा दिया है कि इन माता पिता नोड्स रूट नोड का हिस्सा नहीं है माता पिता नोड्स के किसी भी संख्या के द्वारा साझा किया जा सकता है।

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

   डेटा संरचना ख के रूप में ऐसी है:

2. एक वैध संयोजन एक और संयोजन

इस उदाहरण केवल दो मान्य संयोजनों सीमा के अन्दर संभव हो रहे हैं में से एक सबसेट नहीं होना चाहिए शाखा वस्तुओं की एक सूची है, जिसमें गुण आर, सी और पी हैं, उदाहरण:

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

Answer 1

यह समस्या आसानी से और सुंदर ढंग से पाइथन में हल की जा सकती है, क्योंकि "itertools" नामक एक मॉड्यूल है।

आइए कहें कि हमारे पास हाइपोटेटिकल ब्रंच का प्रकार है, जिसमें गुण आर, पी और सी हैं। बस के रूप में आप इसे अपनी पोस्ट में वर्णित:

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) 

काल्पनिक शाखाओं में से आपका सेट इस प्रकार

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

जादुई समारोह है कि सभी संभव शाखा कॉम्बो की सूची लौटाता है तो तरह लिखा जा सकता है:

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

सटीक होने के लिए, यह फ़ंक्शन एक पुनरावर्तक देता है। इस पर पुनरावृत्ति करके सूची प्राप्त करें। कोड के इन चार लाइनों के लिए सभी संभव कॉम्बो बाहर प्रिंट होगा: ...

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) 

जो है तुम बस क्या चाहता था:

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

इस कार्यक्रम का उत्पादन होता है।

तो स्क्रिप्ट क्या करता है? यह प्रत्येक संयोजन (रूट नोड, बाल नोड) के लिए सभी काल्पनिक शाखाओं की एक सूची बनाता है। और फिर यह इन सूचियों के उत्पाद को उत्पन्न करता है, यानी प्रत्येक सूची में से एक आइटम के सभी संभावित संयोजन।

मुझे आशा है कि मुझे मिल गया क्या आप वास्तव में चाहते थे।

Answer 2

आप दूसरी बाधा का मतलब है कि आप अधिकतम संयोजन चाहते हैं, यानी सभी संयोजन जो लंबाई के साथ सबसे बड़े संयोजन के बराबर हैं।

मैं पहले "बी" संरचना को पार करने और "सी" नामक एक संरचना बनाने के लिए, प्रत्येक बच्चे नोड में आने वाली सभी शाखाओं को संग्रहीत करने और रूट नोड द्वारा वर्गीकृत किए गए एक संरचना को बनाकर इसका संपर्क करूंगा।

फिर आउटपुट के लिए संयोजन बनाने के लिए, प्रत्येक बच्चे के लिए आप खाली नहीं होने वाले प्रत्येक रूट सेट से एक प्रविष्टि शामिल कर सकते हैं। एल्गोरिदम का ऑर्डर (निष्पादन समय) आउटपुट का ऑर्डर होगा, जो आपको प्राप्त हो सकता है।

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

उदाहरण आप प्रदान किया था::

उदाहरण के लिए, अपने "सी" संरचना, की तरह दिखाई देगा

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

यह काफी आसान होना चाहिए इस दृष्टिकोण का उपयोग कर यह कोड करने के लिए। आपको बस सभी शाखाओं "बी" पर फिर से भरने की जरूरत है और "सी" के लिए डेटा संरचना भरें। फिर एक छोटा रिकर्सिव फ़ंक्शन लिखें जो "सी" के अंदर सभी वस्तुओं के माध्यम से जाता है।

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

प्रत्येक बच्चे ग के लिए काल्पनिक माता-पिता पी (ग) के साथ जड़ों आर (पी (ग) के साथ,,:

यहाँ कोड है (मैं अपने नमूना डेटा परीक्षण के लिए शीर्ष पर डाले गए)), पी (सी) में प्रत्येक रूट आर के लिए पी (सी) से बिल्कुल एक पैरेंट पी चुनें (जैसे कि आर पी की जड़ है) और संयोजन में बी शामिल करें जहां बी पी से सी को जोड़ता है (माना जाता है कि वहां है केवल एक ऐसा बी, जिसका अर्थ है कि यह एक मल्टीग्राफ नहीं है)। संयोजनों की संख्या माता-पिता की संख्या का उत्पाद होगी जिसके द्वारा प्रत्येक बच्चा प्रत्येक रूट से कल्पित रूप से जुड़ा हुआ है।दूसरे शब्दों में, संयोजनों के सेट का आकार सभी बच्चे-रूट जोड़े के hypothetical कनेक्शन के उत्पाद के बराबर होगा। आपके उदाहरण में ऐसे सभी बाल-रूट जोड़े में केवल एक पथ है, आर 1-सी 2 को छोड़कर, जिसमें दो पथ हैं, इस प्रकार संयोजनों के सेट का आकार दो है।

यह किसी अन्य संयोजन का कोई सबसेट नहीं होने की बाधा को संतुष्ट करता है क्योंकि प्रत्येक बच्चे के प्रत्येक रूट के लिए बिल्कुल एक पैरेंट चुनकर, हम संख्या कनेक्शन को अधिकतम करते हैं। इसके बाद किसी भी एज बी को जोड़ने से इसकी जड़ को अपने बच्चे से दो बार जोड़ा जा सकता है, जिसकी अनुमति नहीं है। और चूंकि हम बिल्कुल एक चुन रहे हैं, सभी संयोजन बिल्कुल वही लंबाई होंगे।

इस विकल्प को लागू करने से वांछित संयोजन मिलेंगे।

Answer 4

यहां वास्तव में दो समस्याएं हैं: सबसे पहले, आपको इस समस्या को हल करने के लिए उपयोग किए जाने वाले एल्गोरिदम को काम करने की आवश्यकता है और दूसरी बात, आपको इसे लागू करने की आवश्यकता है (पायथन में)।

---

एल्गोरिथ्म

मुझे लगता होगा कि आप एक अधिक से अधिक शाखाओं के संग्रह चाहते हैं; वह है, एक बार जिसमें आप कोई और शाखा नहीं जोड़ सकते हैं। यदि आप नहीं करते हैं, तो आप अधिकतम संग्रह के सभी सबसेट्स पर विचार कर सकते हैं।

इसलिए, एक बच्चे नोड के लिए हम जितनी संभव हो उतनी शाखाएं लेना चाहते हैं, इस बाधा के अधीन कि कोई भी दो माता-पिता नोड रूट साझा नहीं करते हैं। दूसरे शब्दों में, प्रत्येक बच्चे से आप प्रत्येक रूट नोड के पड़ोस में सबसे अधिक किनारे पर हो सकते हैं। ऐसा लगता है कि आप बच्चों पर पहले, फिर (रूट्स नोड्स के पड़ोस), और अंत में इन दोनों किनारों पर फिर से शुरू करना चाहते हैं। हालांकि मैं यह परीक्षण नहीं किया,

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

find all combinations of permissible edges 

---

कोड

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

ऊपर काम करने के लिए लगता है: इस अवधारणा को निम्नलिखित स्यूडोकोड देता है।